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
    \
     2
    /
   3

return[3,2,1].

2. Implementation

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode curNode = null, preNode = null;

        while (!stack.isEmpty()) {
            curNode = stack.peek();
            // Case 1: Traverse down the tree, put left child into stack if it exists, otherwise put right child
            if (preNode == null || preNode.left == curNode || preNode.right == curNode) {
                if (curNode.left != null) {
                    stack.push(curNode.left);
                }
                else if (curNode.right != null) {
                    stack.push(curNode.right);
                }
            }
            // Case 2: Travese up from left child
            else if (curNode.left == preNode) {
                if (curNode.right != null) {
                    stack.push(curNode.right);
                }
            }
            // Case 3: Traverse up from right child
            else {
                res.add(curNode.val);
                stack.pop();
            }
            preNode = curNode;
        }
        return res;
    }
}

3. Time & Space Complexity

时间和空间复杂度都是O(n)