题目描述: 请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
这题几乎和「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) 。