Star

Leetcode 145. Binary Tree Postorder Traversal

Posted on | In |

Question

Given a binary tree, return the postorder traversal of its nodes' values.

For example: Given binary tree {1,#,2,3}, 

1
2
3
4
5
1
 \
  2
 /
3

return [3,2,1].

Explanation

比之前做的preorder和inorder要难些，这里用了一个巧妙的办法，每次加在前面addfirst。如果不这样的话，就需要记录是否visit过了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    // Recursive Solution:
    public List<Integer> postorderTraversal(TreeNode root) {
         List<Integer> result = new ArrayList<>();
         if (root == null) return result;
         List<Integer> left = postorderTraversal(root.left);
         List<Integer> right = postorderTraversal(root.right);
         result.addAll(left);
         result.addAll(right);
         result.add(root.val);
         return result;
    }
    // Iterative Solution:
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        TreeNode tmp = root;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            result.addFirst(cur.val);
            if (cur.left != null) {
                stack.push(cur.left);
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
        }
        return result;
    }
}