Java short Iterative with one queue, and no additional processing of the adding list


  • 0
    C

    Feel free to comment! :)

    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> ans = new ArrayList();
            if (root==null) return ans;
    
            boolean leftToRight = true;
            Queue<TreeNode> q = new LinkedList();
            q.add(root);
            int size = q.size();                   // we use size to keep track of # of items in level
            List<Integer> newList = new ArrayList();
    
            while (!q.isEmpty()){
                TreeNode n = q.poll();
                size--;
    
                if (leftToRight) newList.add(n.val); // when left to right, stuff the list from the right
                else newList.add(0, n.val);             // when right to left, stuff the list from the left
    
                if (n.left!=null) q.add(n.left);           // With the leftToRight stuff we do, 
                if (n.right!=null) q.add(n.right);      // we can always, just add left node then right
    
                if (size==0){
                    ans.add(newList);                     // clean up and create new list and after level is done
                    size = q.size();
                    leftToRight = !(leftToRight);
                    newList = new ArrayList();
                }
            }
            return ans;
        }
    }

  • 0
    N

    Also, we don't need an additional boolean flag, instead use ans.size() to decide the direction:

    ans.size() % 2 != 0: reverse()


  • 0
    C

    Doesn't the reverse() gonna cost you sometime?
    The flag is just one extra variable but will save time not need to do the reverse.

    Or am I missing your point?


Log in to reply
 

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