104. Maximum Depth of Binary Tree

原题：104. Maximum Depth of Binary Tree

方法一

思路：DFS + recursive
时间复杂度：O(n)

// Runtime: 68 ms, faster than 33.83% of JavaScript online submissions for Maximum Depth of Binary Tree.
// Memory Usage: 38.5 MB, less than 6.25% of JavaScript online submissions for Maximum Depth of Binary Tree.
var maxDepth = function (root) {
  if (!root) {
    return 0;
  }

  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

方法二

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

// Runtime: 88 ms, faster than 15.71% of JavaScript online submissions for Maximum Depth of Binary Tree.
// Memory Usage: 40.1 MB, less than 6.25% of JavaScript online submissions for Maximum Depth of Binary Tree.
var maxDepth = function (root) {
  if (!root) {
    return 0;
  }

  const queue = [[root, 0]];
  let maxLevel = 0;
  while (queue.length) {
    const [node, level] = queue.shift();
    maxLevel = Math.max(maxLevel, level);
    node.left && queue.push([node.left, level + 1]);
    node.right && queue.push([node.right, level + 1]);
  }

  return maxLevel + 1;
};

test cases

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

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

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