LeetCode-111. 二叉树的最小深度

不念不忘少年蓝@ 2024-03-27 15:57 59阅读 0赞

#### 目录 ####

*   *  题目分析
     *  递归法

题目来源  
[111. 二叉树的最小深度][111.]

### 题目分析 ###

这道题目容易联想到104题的最大深度，把代码搬过来

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

![在这里插入图片描述][624b9a0e1b12480ba9d7a0e10e13a2fa.png]  
然后仔细读题  
最小深度是从根节点到**最近叶子节点**的最短路径上的节点数量。  
![在这里插入图片描述][8f420fa048714ae7bd15fabcd8a87dd9.png]  
![在这里插入图片描述][108d0e8a6cad491f946c8acad25ab0ac.png]  
为了满足题目需求, 需要额外加上一个条件

if(root.left == null && root.right != null)
    if(root.left != null && root.right == null)

### 递归法 ###

**递归三部曲**

*  1.确定递归函数的参数和返回值

参数为要传入的二叉树根节点，返回的是int类型的深度。  
代码如下：

int dfs(TreeNode root)

*  2.确定终止条件

终止条件也是遇到空节点返回0，表示当前节点的高度为0。  
代码如下：

if(root == null){
        
                return 0;
            }

*  3.确定单层递归的逻辑

这块和求最大深度可就不一样了  
如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。  
反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

int leftDepth = dfs(root.left);   // 左
            int rightDepth = dfs(root.right);    // 右
            // 中
            // 当一个左子树为空，右不为空，这时并不是最低点                                             
            if(root.left == null && root.right != null){
           
                return rightDepth + 1;
            }
            // 当一个右子树为空，左不为空，这时并不是最低点
            if(root.left != null && root.right == null){
        
                return leftDepth + 1;
            }
            return Math.min(leftDepth,rightDepth)+1;

遍历的顺序为后序（左右中），可以看出：**求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。**  
**整体递归代码**

class Solution {
        
        public int minDepth(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }
            return dfs(root);
        }
        public static int dfs(TreeNode root){
        
            if(root == null){
        
                return 0;
            }
            int leftDepth = dfs(root.left);   // 左
            int rightDepth = dfs(root.right);    // 右
            // 中
            // 当一个左子树为空，右不为空，这时并不是最低点                                             
            if(root.left == null && root.right != null){
           
                return rightDepth + 1;
            }
            // 当一个右子树为空，左不为空，这时并不是最低点
            if(root.left != null && root.right == null){
        
                return leftDepth + 1;
            }
            return Math.min(leftDepth,rightDepth)+1;
        }
    }

![在这里插入图片描述][577d8a8356304b879d099f1b2f5d7901.png]

[111.]: https://leetcode.cn/problems/minimum-depth-of-binary-tree/
[624b9a0e1b12480ba9d7a0e10e13a2fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/7b3a630f08484d33bf6f5adf5630eb02.png
[8f420fa048714ae7bd15fabcd8a87dd9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/991454b44ec54d20bbfb54a043074ca9.png
[108d0e8a6cad491f946c8acad25ab0ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/3bb0945100bf4d8794bdddc540f69661.png
[577d8a8356304b879d099f1b2f5d7901.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/6962287b78854520a7472bae3c53e291.png