leetcode-103.png

和 102.二叉树的层序遍历一样，只不过是正一次，反一次

下面这种解法不是很高效，每次都要reverse一下

var zigzagLevelOrder = function (root) {
    if (!root) {
        return []
    }
    let flag = true
    let res = []
    let queue = []
    queue.push(root)
    while (queue.length) {
        let size = queue.length
        let level = []
        for (let i = 0; i < size; ++i) {
            let node = queue.shift()
            level.push(node.val)
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        let tmp = flag ? level : level.reverse()
        flag = !flag
        res.push(level)
    }
    return res
};

直接计算每次要插入地方的下表即可
level[index] = node.val

BFS

var zigzagLevelOrder = function (root) {
    if (!root) {
        return []
    }
    let flag = true
    let res = []
    let queue = []
    queue.push(root)
    while (queue.length) {
        let size = queue.length
        let level = []
        for (let i = 0; i < size; ++i) {
            let node = queue.shift()
            let index = flag ? i : size - i - 1
            level[index] = node.val
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        flag = !flag
        res.push(level)
    }
    return res
};

DFS

var zigzagLevelOrder = function (root) {
    if (!root) {
        return []
    }
    let res = []
    var dfs = function (root, level) {
        if (!root) return
        if (res.length === level) {
            res.push([])
        }
        if (level % 2 === 0) {
            res[level].push(root.val)
        } else {
            res[level].unshift(root.val)
        }
        dfs(root.left, level + 1)
        dfs(root.right, level + 1)
    }
    dfs(root, 0)
    return res
};