剑指offer - 从上到下打印二叉树III - JavaScript

题目描述: 请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

# 题目分析

这题几乎和「LeetCode 102.二叉树的层次遍历」完全一样,唯一不同的是行数为奇数的从左到右打印,行数为偶数的从右到左打印。

# 解法:层序遍历

借助 level 变量标记层数,当 level 为偶数的时候,镜像翻转遍历结果。代码实现如下:

// ac地址:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
// 原文地址:https://xxoo521.com/2020-02-20-level-travel-3/

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (!root) return [];
  const queue = [root];
  const res = [];
  let level = 0; // 代表当前层数
  while (queue.length) {
    res[level] = []; // 第level层的遍历结果

    let levelNum = queue.length; // 第level层的节点数量
    while (levelNum--) {
      const front = queue.shift();
      res[level].push(front.val);
      if (front.left) queue.push(front.left);
      if (front.right) queue.push(front.right);
    }
    // 行号是偶数时,翻转当前层的遍历结果
    if (level % 2) {
      res[level].reverse();
    }

    level++;
  }
  return res;
};

时间复杂度是$O(N)$,空间复杂度是$O(N)$。

# 更多资料