94 Binary Tree Inorder Traversal

94. Binary Tree Inorder Traversal

1. Question

Given a binary tree, return the inorder traversal of its nodes' values.
For example: Given binary tree[1,null,2,3],
1
1
2
\
3
2
4
/
5
3
Copied!
return[1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?

2. Implementation

(1) Morris Tree Traversal
1
class Solution {
2
public List<Integer> inorderTraversal(TreeNode root) {
3
List<Integer> res = new ArrayList<>();
4
if (root == null) {
5
return res;
6
}
7
8
TreeNode curNode = root, preNode = null;
9
10
while (curNode != null) {
11
if (curNode.left == null) {
12
res.add(curNode.val);
13
curNode = curNode.right;
14
}
15
else {
16
preNode = curNode.left;
17
while (preNode.right != null && preNode.right != curNode) {
18
preNode = preNode.right;
19
}
20
21
if (preNode.right == null) {
22
preNode.right = curNode;
23
curNode = curNode.left;
24
}
25
else {
26
res.add(curNode.val);
27
preNode.right = null;
28
curNode = curNode.right;
29
}
30
}
31
}
32
return res;
33
}
34
}
Copied!
(2) Iteration
1
public class Solution {
2
public List<Integer> inorderTraversal(TreeNode root) {
3
List<Integer> res = new ArrayList<>();
4
5
// Method 1: Iterative Stack
6
TreeNode curNode = root;
7
Stack<TreeNode> stack = new Stack<>();
8
9
while (curNode != null || !stack.isEmpty()) {
10
if (curNode != null) {
11
stack.push(curNode);
12
curNode = curNode.left;
13
}
14
else {
15
curNode = stack.pop();
16
res.add(curNode.val);
17
curNode = curNode.right;
18
}
19
}
20
return res;
21
}
22
}
Copied!

3. Time & Space Complexity

(1) Morris Tree Traversal: 时间复杂度: O(n), 空间复杂度: O(1)
(2) Iteration: 时间复杂度: O(n), 空间复杂度:O(h)
Last modified 2yr ago