One stack solution


  • 0
    N
       public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> ans = new LinkedList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode t = root;
            TreeNode pre = t;
            while(t!=null){
                if(pre == t && t.left != null){//first touch t, and t has left child
                        stack.push(t);
                        t = t.left;     
                        pre = t;
                }
                else if((pre == t||pre == t.left) && t.right!=null){// first touch t/second touch t from left child and has right child
                        stack.push(t);
                        t = t.right;
                        pre = t;
                }
                else{
                    ans.add(t.val);
                    pre = t;
                    if(stack.isEmpty()) break;
                    t = stack.pop();
                }
            }
                return ans;
        }
            
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.