My Java solution with one queue and boolean flag to control direction


  • 1
    C
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root==null)return result;
        Queue<TreeNode> queue  = new LinkedList<TreeNode>();
        queue.add(root);
        //boolean flag to mark current line's direction
        boolean isLeftToRight=true;
        List<Integer> level;
        while(!queue.isEmpty()){
            Queue<TreeNode> nextLevel = new LinkedList<TreeNode>();
            level= new ArrayList<Integer>();
            //keep populating current level until done
            for(TreeNode node:queue){
                level.add(node.val);
                if(node.left!=null){
                    nextLevel.add(node.left);
                }
                if(node.right!=null){
                    nextLevel.add(node.right);
                }    
            }
            //before save level list to result, if current line is from left to right, save as is.
            //otherwise, reverse the level before save to result.
    
            if(!isLeftToRight){
                Collections.reverse(level);
            }
            //switch the direction flag when proceeding next level
            isLeftToRight=isLeftToRight?false:true;
            result.add(level);
            queue = nextLevel;
        }
        return result;
    }
    

    Inline comments added in code. Time complexity should be O(N).


  • 0
    B

    Is this "one queue"? You create one queue in every loop! :)


Log in to reply
 

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