102. Binary Tree Level Order Traversal

2020-05-23

原题：102. Binary Tree Level Order Traversal

方法一

思路：BFS
时间复杂度：O(n)

// Runtime: 72 ms, faster than 19.61% of JavaScript online submissions for Binary Tree Level Order Traversal.
// Memory Usage: 35.6 MB, less than 5.88% of JavaScript online submissions for Binary Tree Level Order Traversal.
var levelOrder = function (root) {
  if (!root) {
    return [];
  }

  const queue = [[root, 0]];
  const result = [];
  while (queue.length) {
    const [node, index] = queue.shift();
    result[index] = result[index] || [];
    result[index].push(node.val);
    node.left && queue.push([node.left, index + 1]);
    node.right && queue.push([node.right, index + 1]);
  }
  
  return result;
};

方法二

思路：和方法一的思路类似，也是通过层级计数，不过通过DFS实现
时间复杂度：O(n)

// Runtime: 68 ms, faster than 21.98% of JavaScript online submissions for Binary Tree Level Order Traversal.
// Memory Usage: 35.4 MB, less than 5.88% of JavaScript online submissions for Binary Tree Level Order Traversal.
var levelOrder = function (root, result = [], level = 0) {
  if (!root) {
    return result;
  }

  result[level] = result[level] || [];
  result[level].push(root.val);
  root.left && levelOrder(root.left, result, level + 1);
  root.right && levelOrder(root.right, result, level + 1);

  return result;
};

方法三

思路：BFS + Batch Process
时间复杂度：O(n)

// Runtime: 64 ms, faster than 30.81% of JavaScript online submissions for Binary Tree Level Order Traversal.
// Memory Usage: 35.7 MB, less than 5.88% of JavaScript online submissions for Binary Tree Level Order Traversal.
var levelOrder = function (root) {
  if (!root) {
    return [];
  }
  const queue = [root];
  const result = [];
  while (queue.length) {
    let level = [];
    for (let i = 0, len = queue.length; i < len; i++) {
      //注意这里把层节点数记录了下来
      const node = queue.shift();
      level.push(node.val);
      node.left && queue.push(node.left);
      node.right && queue.push(node.right);
    }
    result.push(level);
  }

  return result;
};

test cases

test("test1", () => {
  expect(levelOrder(makeTree([3, 9, 20, null, null, 15, 7]))).toEqual([
    [3],
    [9, 20],
    [15, 7],
  ]);
});

test("test2", () => {
  expect(levelOrder(makeTree([]))).toEqual([]);
});

test("test3", () => {
  expect(levelOrder(makeTree([1]))).toEqual([[1]]);
});