Skip to main content

103 - 二叉树的锯齿形层序遍历

题目链接

二叉树的锯齿形层序遍历

题目

给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

思路

层序遍历(BFS),根据层数来确定方向。

解题方法

获取当前层的所有节点,根据方向决定是push还是unshift

代码

/**
* @param {TreeNode} root
* @return {number[][]}
*/
var zigzagLevelOrder = function(root) {
if(root === null) {
return [];
}
const stack = [root];
const result = [];
// 0 -> right 1 -> left
let direction = 0;
while(stack.length) {
const layerLenght = stack.length;
result.push([]);
for(let i = 0; i < layerLenght; i++) {
const node = stack.shift();
if(direction === 0) {
result[result.length - 1].push(node.val);
} else {
result[result.length - 1].unshift(node.val);
}

if(node.left) stack.push(node.left);
if(node.right) stack.push(node.right);
}
direction = direction === 0 ? 1 : 0;
}
return result;
};

复杂度分析

  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)