Binary Tree Zigzag Level Order Traversal Medium 0 attempts
LeetCode ↗

Binary Tree Zigzag Level Order Traversal

Medium TreeBinary TreeDFS LeetCode

Given a binary tree, return the zigzag level order traversal (left to right, then right to left for the next level, alternating).

Example: root = [3,9,20,null,null,15,7] → Output: [[3],[20,9],[15,7]]

Sample Input
—
Sample Output
—
Constraints
  • 0 <= number of nodes <= 2000
  • -100 <= Node.val <= 100
Topics
TreeBinary TreeDFS

BFS with Direction Flag

function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [], q = [root];
  let leftToRight = true;
  while (q.length) {
    const level = [], size = q.length;
    for (let i = 0; i < size; i++) {
      const node = q.shift();
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    result.push(leftToRight ? level : level.reverse());
    leftToRight = !leftToRight;
  }
  return result;
}

Time: O(n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript