二叉树的锯齿形层次遍历

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

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
 
function zigzagLevelOrder(root: TreeNode | null): number[][] {
    //层次遍历放入队列的时候反着来
    if (!root) return [];
    const res=[]
    const queue = [root]
    let left_to_right = true
 
    while(queue.length >0){
        let length = queue.length 
        //当前层次所遍历出来的值
        const queue_val = []
        for(let i=0;i<length;i++){
            const node = queue.shift()
            if(left_to_right){
                queue_val.push(node.val)
            }else {
                queue_val.unshift(node.val)
            }
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
        res.push(queue_val)
        left_to_right = !left_to_right
    }
    return res
};