二叉树的Z字形层序遍历
层序遍历
BFS层序遍历,非递归实现,push进入结果数组的时候识别偶数行还是奇数行
- 时间复杂度 O(N),空间复杂度O(N)
- Runtime: 80 ms, faster than 77.53%
- Memory Usage: 40 MB, less than 79.09%
var zigzagLevelOrder = function(root) {
if(root === null) return []
let res = []
let queue = [root]
let level = 0
while(queue.length !== 0) {
let len = queue.length
let sub = []
for(let i = 0; i < len; i++) {
let node = queue.shift()
if(node.left) queue.push(node.left)
if(node.right) queue.push(node.right)
if (level % 2 === 1) sub.unshift(node.val)
else sub.push(node.val)
}
res.push(sub)
level++
}
return res
};
递归
- 时间复杂度O(N),空间复杂度O(H)
- Runtime: 80 ms, faster than 77.53%
- Memory Usage: 40 MB, less than 79.09%
var zigzagLevelOrder = function(root) {
var res = []
recursive(root, 0, res)
return res
};
var recursive = function(root, level, res){
if (root === null) return
if (res[level]){
if (level % 2 === 1) res[level].unshift(root.val)
else res[level].push(root.val)
}else{
res[level] = [root.val]
}
recursive(root.left, level + 1, res)
recursive(root.right, level + 1, res)
}