Leetcode 145. Binary Tree Postorder Traversal

Description:

Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3}.

return [3,2,1].

Thinking:

The main idea is same as preorder and inorder tranversal in the recursion way. it's a little bit challenge to do it iteratively. Because when we pop() TreeNode, we should make sure whether its right subtree has already tranversed.

Steps:

Code:

public class Solution {
    TreeNode right = null;
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<Integer>();
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while(!stack.isEmpty()||current != null){
            while(current != null){
                stack.push(current);
                current = current.left;
            }
            current = stack.peek();
            if(current.right == null || current.right == right){
                result.add(current.val);
                stack.pop();
                right = current;
                current = null;
            }
            else{
                current = current.right;
            }

        }
        return result;
    }
}

Recursion(with helper)

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null)return new ArrayList<Integer>();
        List<Integer> result = new ArrayList<>();
        postorderTraversalhelper(root,result);
        return result;
    }
    private void postorderTraversalhelper(TreeNode root, List<Integer> result){
        if(root == null) return;
        postorderTraversalhelper(root.left, result);
        postorderTraversalhelper(root.right, result);
        result.add(root.val);
    }
}

Recursion(no helper)

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null)return new ArrayList<Integer>();
        List<Integer> result = new ArrayList<>();
        List<Integer> left = postorderTraversal(root.left);
        List<Integer> right = postorderTraversal(root.right);
        result.addAll(left);
        result.addAll(right);
        result.add(root.val);
        return result;
    }
}

Conclusion:

peek() is the key for the iterative way. If we met the situation that we are not sure whether we should pop() this node. We can peek() first to decide.

Leetcode 145. Binary Tree Postorder Traversal