Accepted iterative Java solution using two stacks


  • -2
    W
    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
                    ArrayList<Integer> result = new ArrayList<Integer>();
    
            if(root == null)return result;
            
            Stack<Integer> flags = new Stack<Integer>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
        
            TreeNode p = root;
            
            do{
                while(p!=null){ // go to leftmost node
                    stack.push(p);
                    flags.push(0); // not visited
                    
                    p = p.left;
                }
                p = stack.top();
                // visit node
                if(flags.top()==0){ // not visited, go to right child first
                    p = p.right;
                    flags.pop();
                    flags.push(1); // visited
                    
                }else{ // already visited once, now pop it and save int value
                    p = stack.pop();
                    // remember to pop flag too
                    flags.pop();
                    
                    result.add(p.val);
                    p = null; // avoid infinite loop
                }
       
            }while(stack.count()>0);
            
            return result;
        }
        
        class Stack<T> {
            
            StackNode<T> top = null;
            private int count = 0;
            
            public int count() {
                return this.count;
            }
            public void push(T t){
                
                StackNode<T> n = new StackNode(t);
                
                n.next = top;
                top = n;
                
                this.count++;
            }
            public T pop(){
                
                if(this.count==0)return null;
                T temp = this.top.val;
                this.top = this.top.next;
                this.count--;
                
                return temp;
            }
            public T top(){
                if(this.top == null)return null;
                return this.top.val;
            }
        }
        class StackNode<T> {
            
            T val;
            StackNode<T> next;
            
            public StackNode(T t) {
                this.val = t;
            }
        }
    }

Log in to reply
 

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