111. Minimum Depth of Binary Tree

原题：111. Minimum Depth of Binary Tree

方法一

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

// Runtime: 80 ms, faster than 17.32% of JavaScript online submissions for Minimum Depth of Binary Tree.
// Memory Usage: 38.4 MB, less than 20.00% of JavaScript online submissions for Minimum Depth of Binary Tree.
var minDepth = function (root) {
  if (!root) {
    return 0;
  }

  if (root.left && root.right) {
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
  } else if (root.left) {
    return 1 + minDepth(root.left);
  } else if (root.right) {
    return 1 + minDepth(root.right);
  } else {
    return 1;
  }
};

方法二

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

// Runtime: 72 ms, faster than 21.72% of JavaScript online submissions for Minimum Depth of Binary Tree.
// Memory Usage: 40.6 MB, less than 20.00% of JavaScript online submissions for Minimum Depth of Binary Tree.
var minDepth = function (root) {
  if (!root) {
    return 0;
  }

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

  return minLevel + 1;
};

test cases

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

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

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

test("test4", () => {
  expect(minDepth(makeTree([1, 2]))).toEqual(2);
});