Simple Java solution


  • 0
    B

    keep a count for current and next level
    And go to next level when current nodes are traversed and also change traverse direction.

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

        List<List<Integer>> list = new ArrayList();
        if(root == null) return list;
        
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        boolean isRight = true;
        
        int curCount = 1;
        int nextCount = 0;
        
        queue.addLast(root);
        
        LinkedList<Integer> l = new LinkedList<Integer>();
        list.add(l);
        
        while(!queue.isEmpty()){
            TreeNode node = queue.remove(0);
            if(isRight)
                l.addLast(node.val);
            else l.addFirst(node.val);
            
            curCount--;
            
            if(node.left != null){
                queue.addLast(node.left);
                nextCount++;
            }
            
            if(node.right != null){
                queue.addLast(node.right);
                nextCount++;
            }
            
            if(curCount == 0 && nextCount != 0){
                l = new LinkedList<Integer>();
                list.add(l);
                curCount = nextCount;
                nextCount = 0;
                
                isRight = !isRight;
            }
                
        }
        
        
        return list;
    }
    

    ''''


Log in to reply
 

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