Java Solution using Double Ended Queues


  • 0

    '''

    public class Solution {

    List<List<Integer>> ll = new ArrayList<List<Integer>>(); 
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Deque<TreeNode> dq = new LinkedList<TreeNode>();
        
        int currentLevel = 1;
        int nextLevel = 0;
        
        // left, right, left 
        int alternating = 2;
        
        if (root != null) {
            dq.addLast(root);
        } else {
            return ll;
        }
        
        List<Integer> l = new ArrayList<Integer>();
        
        while (!dq.isEmpty()) {
            
            // east direction
            if (alternating % 2 == 0) {
                if (currentLevel == 0) {
                    l = new ArrayList<Integer>();
                    currentLevel = nextLevel;
                    nextLevel = 0; 
                }
                
                TreeNode temp = dq.removeLast(); 
                l.add(temp.val);
                
                currentLevel--;
                
                
                
                if (temp.left != null) {
                    dq.addFirst(temp.left);
                    nextLevel++;
                }
                
                if (temp.right != null) {
                    dq.addFirst(temp.right);
                    nextLevel++;
                } 
                
                
                if (currentLevel == 0) {
                    ll.add(l);
                    alternating++; 
                }
                
                
            } else {
                // west direction
                if (currentLevel == 0) {
                    l = new ArrayList<Integer>();
                    currentLevel = nextLevel; 
                    nextLevel = 0;
                    
                }
                
                TreeNode temp = dq.removeFirst();
                l.add(temp.val);
                
                currentLevel--;
                
                
                if (temp.right != null) {
                    dq.addLast(temp.right);
                    nextLevel++;
                }
                
                if (temp.left != null) {
                    dq.addLast(temp.left);
                    nextLevel++; 
                }
                
                if (currentLevel == 0) {
                    ll.add(l);
                    alternating++; 
                }
            }
            
            
            
        }
        return ll; 
        
    }
    

    }
    '''


Log in to reply
 

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