144 Binary Tree Preorder Traversal

144. Binary Tree Preorder Traversal

1. Question

Given a binary tree, return thepreordertraversal of its nodes' values.
For example: Given binary tree{1,#,2,3},
1
1
2
\
3
2
4
/
5
3
Copied!
return[1,2,3].

2. Implementation

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

3. Time & Space Complexity

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