給你二叉樹的根節(jié)點 root ，返回其節(jié)點值的 鋸齒形層序遍歷 。（即先從左往右，再從右往左進行下一層遍歷，以此類推，層與層之間交替進行）。

示例：

輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[20,9],[15,7]]

自己的解法：利用stack和lStack兩個隊列，在lStack中改控制方向

function zigzagLevelOrder(root: TreeNode | null): number[][] {
  let res = []
  let rtl = true
  let stack: Array<TreeNode> = []
  if (root === null) return []
  stack.push(root)
  while (stack.length) {
    let size = stack.length
    let lStack = []
    res.push([])
    rtl = !rtl
    for(let i = 1; i <= size; i++) {
      let node = stack.shift()
      res[res.length - 1].push(node.val)
      lStack.push(node)
    }
    while(lStack.length) {
      let lNode = lStack.pop()
      if (rtl) {
        if (lNode.left) stack.push(lNode.left)
        if (lNode.right) stack.push(lNode.right)
      } else {
        if (lNode.right) stack.push(lNode.right)
        if (lNode.left) stack.push(lNode.left)
      }
    }
  }
  return res
};

其實利用雙端隊列更簡便，只需要一個隊列完成需求：

• 如果從左至右，我們每次將被遍歷到的元素插入至雙端隊列的末尾。
• 如果從右至左，我們每次將被遍歷到的元素插入至雙端隊列的頭部。

function zigzagLevelOrder(root: TreeNode | null): number[][] {
    if (!root) {
        return [];
    }

    const ans = [];
    const nodeQueue = [root];
    let isOrderLeft = true;

    while (nodeQueue.length) {
        let levelList = [];
        const size = nodeQueue.length;
        for (let i = 0; i < size; ++i) {
            const node = nodeQueue.shift();
            if (isOrderLeft) {
                levelList.push(node.val);
            } else {
                levelList.unshift(node.val);
            }
            if (node.left !== null) {
                nodeQueue.push(node.left);
            }
            if (node.right !== null) {
                nodeQueue.push(node.right);
            }
        }            
        ans.push(levelList);
        isOrderLeft = !isOrderLeft;
    }
    return ans;
};