题目

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

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

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

示例:

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最小深度 2

思路

深度优先 + 分治

  • 左右子树都不为空:左子树深度和右子树最小深度的最小值 + 1
  • 左树为空:右子树最小深度的最小值 + 1
  • 右树为空:左子树最小深度 + 1

代码

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

考察点

  • 二叉树
  • 递归
  • 分治
Last Updated: 8/2/2019, 10:05:56 PM