剑指 Offer 32 - III. 从上到下打印二叉树 III

中等
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：

[
[3],
[20,9],
[15,7]
]

提示：
节点总数 <= 1000
方法一：层序遍历+奇偶逻辑分离

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(root==null) return []
    let direction = true//true 为左子树
    let res = []
    let queue = [root]
    while(queue.length!=0){
        let temp = []
        for(let i =queue.length;i>0;i--){
            let node = null
            if(direction){
                node = queue.shift()
            }else{
                node = queue.pop()
            }
            temp.push(node.val)
            if(direction){
                if(node.left!=null) queue.push(node.left)
                if(node.right!=null) queue.push(node.right)
            }else{
                if(node.right!=null) queue.unshift(node.right)
                if(node.left!=null) queue.unshift(node.left)
            }
        }
        direction=!direction
        res.push(temp)
    }
    return res
};

方法二：层序遍历+双端队列

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(root==null) return []
    let res = []
    let queue = [root]
    while(queue.length!=0){
        let temp = []
        for(let i =queue.length;i>0;i--){
            let node = queue.shift()
            if(res.length%2==0){
                temp.push(node.val)
            }else{
                temp.unshift(node.val)
            }
            if(node.left!=null) queue.push(node.left)
            if(node.right!=null) queue.push(node.right)
        }
        res.push(temp)
    }
    return res
};

方法三：层序遍历+倒序数组

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(root==null) return []
    let res = []
    let queue = [root]
    while(queue.length!=0){
        let temp = []
        for(let i =queue.length;i>0;i--){
            let node = queue.shift()
            temp.push(node.val)
            if(node.left!=null) queue.push(node.left)
            if(node.right!=null) queue.push(node.right)
        }
        if(res.length%2==1) temp.reverse()
        res.push(temp)
    }
    return res
};