[LeetCode] 145. Binary Tree Postorder Traversal

Posted on | In

Problem

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

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

Explanation 1

  1. Postorder traversal is from left->right->root.

  2. We can use recursion to solve it. First, think of a tree that only has 3 nodes, root node, left and right nodes. Then we want to add the left node first, so we think of another tree and its root node is the previous tree’s left child node, then recursivly, we check this node’s left child, it’s null, we return nothing, then check its right child, which is also null, we return nothing, then we add this root node to the result array. It means when left and right children is null, then we can add that root node (which is the original tree’s left child) to our result array. In other word, we recursivly check the original tree’s left child first, then the right child, then adding the root node.

Solution 1

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    void helper(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        helper(root.left, res);
        helper(root.right, res);
        res.add(root.val);
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        helper(root, res);
        return res;
    }
}

Explanation 2

  1. We can also do it iterativly. Similar to 144. Binary Tree Preorder Traversal, preorder is root->left->right. Now postorder is left->right->root, and now we can think of adding the node at the beginning each time, so we want to add root first, then right, then left, in other word, root->right->left, which is similar to preorder. We just need to switch the left and right node from the preorder traversal method.

Solution 2

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null) return res;
        Stack<TreeNode> st = new Stack<>();
        TreeNode p = root;

        while (!st.isEmpty() || p != null) {
            if (p != null) {
                st.push(p);
                res.offerFirst(p.val);
                p = p.right;
            } else {
                TreeNode popNode = st.pop();
                p = popNode.left;
            }
        }

        return res;
    }
}