[LeetCode] Binary Tree Postorder Traversal

Problem:

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].

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

Solution:O(n)

public class Solution {
    public ArrayList postorderTraversal(TreeNode root) {
        ArrayList lst = new ArrayList();
        if(root == null)
            return lst; 
 
        Stack stack = new Stack<>();
        stack.push(root);
 
        TreeNode prev = null;
        while(!stack.empty()){
            TreeNode curr = stack.peek();
            if(prev == null || prev.left == curr || prev.right == curr){
                if(curr.left != null){
                    stack.push(curr.left);
                }else if(curr.right != null){
                    stack.push(curr.right);
                }else{
                    stack.pop();
                    lst.add(curr.val);
                }
            }else if(curr.left == prev){
                if(curr.right != null){
                    stack.push(curr.right);
                }else{
                    stack.pop();
                    lst.add(curr.val);
                }
            }else if(curr.right == prev){
                stack.pop();
                lst.add(curr.val);
            }
            prev = curr;
        }
        return lst;
    }
}