[leetcode] 二叉树的锯齿形层序遍历 (双端队列)

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

示例：

输入：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;
};