算法日记-LeetCode-111.二叉树的最小深度

原题链接：111. 二叉树的最小深度 - 力扣（LeetCode）

题目大意

给定一颗二叉树，要求给出根节点到最近的叶子节点的路径所包含的节点个数。

输入：root = [1,2,3,null,null,4,5]
输出：2
说明：1 -> 2 共两个节点

解题思路

递归

叶子节点，其左右子树都为null；我们可以通过判断左右子树来确定叶子节点，然后就需要计算出根节点到当前叶子节点的路径中包含了多少节点。

如何获取根节点到叶子节点的路径所包含的节点个数？

我们可以这样计算，将二叉树简化为一个根节点和左右两个子树。

根节点到其左子节点的距离就是1（根节点） + 左子节点的对应值

即我们可以不断的从子树获取所需的信息，然后进行相关的计算。

例如：

这里我们要得到节点1到叶子节点4包含的节点数

• 从节点4开始，往左右子节点取值，左右子节点为空，返回0，算上本身，所以是1；

• 然后到节点3，节点3到节点4，节点3自己算一个，所以是1，然后获取节点4的对应值也是1，所以节点3到节点4的距离，可以记录为1（节点3自己） + 1（节点4的值） = 2

• 然后节点1到节点4经过右子节点3，节点1本身加上节点3到节点4的距离2，最后得到节点1到节点4的距离 1 + 2 = 3

故按照这个思路，我们可以求得根节点到每一个叶子节点的值，最后取其中最小的即为符合题意的解。

代码

递归解法：

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right != null) {
            return 1 + minDepth(root.right);
        }
        if (root.right == null && root.left != null) {
            return 1 + minDepth(root.left);
        }
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }
}