# [LeetCode 103] TypeScript 双向队列 + BFS

“一见层次遍历,立刻想到队列,立刻想到BFS,我的想像惟在这一层能够如此跃进。”

这个题其实跟普通的层次遍历区别不大,但是因为多了个锯齿形,所以单向队列就不太够用了,需要双向队列。而ts / js的数组本身就是双向队列,特别适合这个场景。别的直接套BFS的模板就行了。

function zigzagLevelOrder(root: TreeNode | null): number[][] {
  const res: number[][] = [];
  if (!root) return res;
  const deque = [root];
  let step = 0;
  while (deque.length) {
    const current_layer = [];
    let length = deque.length;
    if (step % 2 === 0) {
      for (let i = 0; i < length; ++i) {
        const current = deque.shift()!;
        current_layer.push(current.val);
        if (current.left) deque.push(current.left);
        if (current.right) deque.push(current.right);
      }
    } else {
      for (let i = 0; i < length; ++i) {
        const current = deque.pop()!;
        current_layer.push(current.val);
        if (current.right) deque.unshift(current.right);
        if (current.left) deque.unshift(current.left);
      }
    }
    if (current_layer.length) {
      res.push(current_layer);
    }
    ++step;
  }
  return res;
}
最后更新于: 6/25/2020, 2:10:06 PM