二叉树的最小深度（递归）

问题重述：

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

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

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

问题分析：

这道题要求我们找到二叉树的最小深度，那么就是要我们找到所有的叶子节点，并且再找到叶子结点的时候知道此时树的深度。

解法：

递归

解题：

代码：

public int minDepth(TreeNode root) {
        return minDepthProcess(root,1);
    }
// 原题只给了我们一个根节点，要求返回一个最小深度，我们需要自己再创建一个方法来实现
    public int minDepthProcess(TreeNode root,int minDepth){
        // 当根节点为null的时候，返回0
        if(root == null){
            return 0;
        }
        // 当前结点不为null，并且为叶子节点，将当前的深度返回（这就是递归退出条件）
        if(root.left == null && root.right == null){
            return minDepth;
        }
        int res = Integer.MAX_VALUE;
        if(root.left != null){
            // 当当前节点的左子节点不为null的时候，向左递归，最后的到的值是当前左树点中的最小深度
            res = Math.min(minDepthProcess(root.left,minDepth+1),res);
        }
        if(root.right != null){
            // 当当前的右子节点不为null的时候，向右递归，得到的是当前结点的子树中的最小深度（因为在此之前当前节点的左子树的最小深度就是res，因此现在向右递归，得到的是右子树中的最小深度，res就是子树的最小深度）
            res = Math.min(minDepthProcess(root.right,minDepth+1),res);
        }
        return res;
    }

代码解析：

递归的三要素：

递归停止条件：当前结点为叶子结点

递归中重复的操作：得到当前结点的最小深度，也就是调用我们自己这个方法，然后对参数进行修改

进入下一次递归：分别对左子树和右子树进行递归