145 Binary Tree Postorder Traversal

145. Binary Tree Postorder Traversal

1. Question

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

2. Implementation

(1) Morris Tree Traversal
1
class Solution {
2
public List<Integer> postorderTraversal(TreeNode root) {
3
List<Integer> res = new ArrayList<>();
4
if (root == null) {
5
return res;
6
}
7
8
TreeNode dummy = new TreeNode(0);
9
dummy.left = root;
10
TreeNode curNode = dummy, preNode = null;
11
12
while (curNode != null) {
13
if (curNode.left == null) {
14
curNode = curNode.right;
15
}
16
else {
17
preNode = curNode.left;
18
while (preNode.right != null && preNode.right != curNode) {
19
preNode = preNode.right;
20
}
21
// Traversing down to the left
22
if (preNode.right == null) {
23
preNode.right = curNode;
24
curNode = curNode.left;
25
}
26
// Traversing up from the right
27
else {
28
TreeNode node = preNode;
29
reverse(curNode.left, preNode);
30
while (node != curNode.left) {
31
res.add(node.val);
32
node = node.right;
33
}
34
res.add(node.val);
35
reverse(preNode, curNode.left);
36
preNode.right = null;
37
curNode = curNode.right;
38
}
39
}
40
}
41
return res;
42
}
43
44
public void reverse(TreeNode from, TreeNode to) {
45
if (from == to) {
46
return;
47
}
48
49
TreeNode preNode = from, curNode = from.right, nextNode = null;
50
while (preNode != to) {
51
nextNode = curNode.right;
52
curNode.right = preNode;
53
preNode = curNode;
54
curNode = nextNode;
55
}
56
}
57
}
Copied!
(2) Iteration
1
class Solution {
2
public List<Integer> postorderTraversal(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, preNode = null;
12
13
while (!stack.isEmpty()) {
14
curNode = stack.peek();
15
// Case 1: Traverse down the tree, put left child into stack if it exists, otherwise put right child
16
if (preNode == null || preNode.left == curNode || preNode.right == curNode) {
17
if (curNode.left != null) {
18
stack.push(curNode.left);
19
}
20
else if (curNode.right != null) {
21
stack.push(curNode.right);
22
}
23
}
24
// Case 2: Travese up from left child
25
else if (curNode.left == preNode) {
26
if (curNode.right != null) {
27
stack.push(curNode.right);
28
}
29
}
30
// Case 3: Traverse up from right child
31
else {
32
res.add(curNode.val);
33
stack.pop();
34
}
35
preNode = curNode;
36
}
37
return res;
38
}
39
}
Copied!

3. Time & Space Complexity

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