103.Binary Tree Zigzag Level Order Traversal

tags: Medium,Tree,BFS,Binary Tree

103. Binary Tree Zigzag Level Order Traversal

題目描述

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

範例

Example 1:

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

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

解答

Javascript

function zigzagLevelOrder(root) {
  if (root === null) return [];
  const result = [];
  const queue = [root];
  let level = 0;
  while (queue.length) {
    const nodes = [];
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (level % 2 === 0) {
        nodes.push(node.val);
      } else {
        nodes.unshift(node.val);
      }

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(nodes);
    level++;
  }

  return result;
}

MarsgoatFeb 20, 2023

Reference

回到題目列表