Java Solution - Easy to Understand


  • 0

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        if (root == null) {
            return Collections.emptyList();
        }
        
        List<List<Integer>> ret = new ArrayList<>(); 
        
        // temp stack to store tree nodes
        Deque<TreeNode> curStack = new ArrayDeque<>();
        List<Integer> curVal = new LinkedList<>();
    
        // initialize stack 
        curStack.add(root); 
        curVal.add(root.val); 
        int level = 0; 
        
        while (!curStack.isEmpty()){
            ret.add(curVal); 
            level++;
            
            Deque<TreeNode> newStack = new ArrayDeque<>();
            List<Integer> newVal = new LinkedList<>();
            
            for (TreeNode cur : curStack){
                // level to decide the direction - right first vs. left first. 
                if (level%2 == 0){
                    if (cur.left != null) {             
                        newStack.addFirst(cur.left); 
                        newVal.add(cur.left.val); 
                    }
                    if (cur.right != null) {      
                        newStack.addFirst(cur.right);
                        newVal.add(cur.right.val);  
                    } 
                } else {
                    if (cur.right != null) {           
                        newStack.addFirst(cur.right); 
                        newVal.add(cur.right.val);  
                    }
                    if (cur.left != null) {          
                        newStack.addFirst(cur.left); 
                        newVal.add(cur.left.val);  
                    }
                }
            }
            
            curStack = newStack; 
            curVal = newVal; 
        }
        
        return ret; 
    }

Log in to reply
 

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