094. 二叉树的中序遍历 - Binary Tree Inorder Traversal
【中序遍历-递归】 【中序遍历-迭代】
给定一个二叉树，返回它的中序遍历。
Example:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
Solutions
1
2
3
4
5
6
7
8
9
|
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
|
Solution 【中序遍历-递归】 ( 0ms)
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
List<Integer> result = new LinkedList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root != null){ //相比 if (root == null) return result; 会快1ms
inorderTraversal(root.left);
result.add(root.val);
inorderTraversal(root.right);
}
return result;
}
}
|
Solution 【中序遍历-迭代】 ( 2ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
if (!stack.isEmpty()) {
current = stack.pop();
result.add(current.val);
current = current.right;
}
}
return result;
}
}
|
Notes