Question

Formatted question description: https://leetcode.ca/all/103.html

103	Binary Tree Zigzag Level Order

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

@tag-tree

Algorithm

Since the number of nodes in each layer is known, that is, the number of elements in the queue, the size of the array can be initialized directly. At this time, a variable leftToRight is used to mark the order.

The initial value is true. When this variable is true, the position that is added to the array is i itself. If the variable is false, it is added to the position of size-1-i. This is directly equivalent to flipping the array. After traversing each level, you need to flip the leftToRight variable, and don’t forget to add oneLevel to the result.

Code

Java

  • public class Binary_Tree_Zigzag_Level_Order_Traversal {
        
        /**
         * Definition for a binary tree node.
         * public class TreeNode {
         * int val;
         * TreeNode left;
         * TreeNode right;
         * TreeNode(int x) { val = x; }
         * }
         */
    
        // count as level marker
        class Solution {
            public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    
                List<List<Integer>> result = new ArrayList<>();
    
                if (root == null) {
                    return result;
                }
    
                boolean isLeftToRight = true;
    
                Queue<TreeNode> q = new LinkedList<>();
                q.offer(root);
    
                int currentLevelCount = 1;
                int nextLevelCount = 0;
    
                List<Integer> one = new ArrayList<>();
    
                while (!q.isEmpty()) {
                    TreeNode current = q.poll();
                    currentLevelCount--;
    
                    if (isLeftToRight) {
                        one.add(current.val);
                    } else {
                        one.add(0, current.val);
                    }
    
                    if (current.left != null) {
                        q.offer(current.left);
                        nextLevelCount++;
                    }
                    if (current.right != null) {
                        q.offer(current.right);
                        nextLevelCount++;
                    }
    
                    if (currentLevelCount == 0) {
                        currentLevelCount = nextLevelCount;
                        nextLevelCount = 0;
    
                        result.add(one);
                        one = new ArrayList<>();
    
                        isLeftToRight = !isLeftToRight;
                    }
                }
    
                return result;
            }
        }
    
        public class Solution_nullAsMarker {
            public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    
                List<List<Integer>> list = new ArrayList<List<Integer>>();
    
                if (root == null) {
                    return list;
                }
    
                Queue<TreeNode> q = new LinkedList<>();
    
                q.offer(root);
                q.offer(null);// @note: use null as marker for end of level
    
                boolean direction = true; // true: left=>right, false: right=>left
                List<Integer> oneLevel = new ArrayList<>();
                while (!q.isEmpty()) {
    
                    TreeNode current = q.poll();
    
                    if (current == null) {
                        List<Integer> copy = new ArrayList<>(oneLevel);
                        list.add(copy);
    
                        // clean after one level recorded
                        oneLevel.clear();// @memorize: this api
                        direction = !direction;
    
                        // @note:@memorize: if stack is now empty then DO NOT add null, or else infinite looping
                        // sk.offer(null); // add marker
                        if (!q.isEmpty()) {
                            q.offer(null); // add marker
                        }
    
                        continue;
                    }
    
                    if (direction) {
                        oneLevel.add(current.val);
                    } else {
                        oneLevel.add(0, current.val);
                    }
    
                    // @note:@memorize: since using null as marker, then must avoid adding null when children are null
                    // sk.offer(current.left);
                    // sk.offer(current.right);
                    if (current.left != null) {
                        q.offer(current.left);
                    }
                    if (current.right != null) {
                        q.offer(current.right);
                    }
    
                }
    
                return list;
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            if (!root) return {};
            queue<TreeNode*> q;
            q.push(root);
            bool l2r = true;
            vector<vector<int>> ans;
            while (q.size()) {
                int cnt = q.size();
                vector<int> lv;
                while (cnt--) {
                    root = q.front();
                    q.pop();
                    lv.push_back(root->val);
                    if (root->left) q.push(root->left);
                    if (root->right) q.push(root->right);
                }
                if (!l2r) reverse(begin(lv), end(lv));
                ans.push_back(lv);
                l2r = !l2r;
            }
            return ans;
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    from collections import deque
    
    
    class Solution(object):
      def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        stack = deque([root])
        ans = []
        odd = True
        while stack:
          level = []
          for k in range(0, len(stack)):
            top = stack.popleft()
            if top is None:
              continue
            level.append(top.val)
            stack.append(top.left)
            stack.append(top.right)
          if level:
            if odd:
              ans.append(level)
            else:
              ans.append(level[::-1])
          odd = not odd
        return ans
    
    

All Problems

All Solutions