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)

144 Binary Tree Preorder Traversal

366 Find Leaves of Binary Tree

Last modified 2yr ago

Copy link

Contents

145. Binary Tree Postorder Traversal

1. Question

2. Implementation

3. Time & Space Complexity