103 Binary Tree Zigzag Level Order Traversal

二叉树的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)
}