32 - 二叉树的最小深度

题目

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

3 / 9 20 / 15 7

返回它的最小深度 2.

解答

深度优先

var minDepth = function (root) {
  if (!root) {
    return 0
  }
  if (!root.left && !root.right) {
    return 1
  }
  let depth = Number.MAX_SAFE_INTEGER
  if (root.left) {
    depth = Math.min(minDepth(root.left), depth);
  }
  if (root.right) {
    depth = Math.min(minDepth(root.right), depth);
  }
  return depth + 1
};

Runtime: 60 ms, faster than 84.99% of JavaScript online submissions for Minimum Depth of Binary Tree.

Memory Usage: 37.6 MB, less than 20.12% of JavaScript online submissions for Minimum Depth of Binary Tree.

看到第二种解法：

作者：user7208t

链接：https://leetcode-cn.com/problems/two-sum/solution/li-jie-zhe-dao-ti-de-jie-shu-tiao-jian-by-user7208/

var minDepth = function (root) {
  if (!root) {
    return 0
  }
  let left = minDepth(root.left)
  let right = minDepth(root.right)
  return !root.left || !root.right ? left + right + 1 : Math.min(left, right) + 1
};

执行用时 :96 ms, 在所有 JavaScript 提交中击败了68.34%的用户

内存消耗 :36.8 MB, 在所有 JavaScript 提交中击败了94.44%的用户

广度优先