【算法题解】34. 二叉树的最小深度

蔚落 2024-03-16 13:45 41阅读 0赞

> 这是一道 **简单** 题  
>   
> https://leetcode.cn/problems/minimum-depth-of-binary-tree/

#### 文章目录 ####

*   *  题目
     *  简单递归解法
     *   *   *  Java 代码实现
             *  Go 代码实现
             *  复杂度分析
     *  DFS
     *   *   *  Java 代码实现
             *  Go 代码实现
             *  复杂度分析
     *  BFS
     *   *   *  Java 代码实现
             *  Go 代码实现
             *  复杂度分析
     *  总结

### 题目 ###

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

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

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

**示例 1：**

![8550e78685022eb28bf1dac398fa1060.png][]

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

**示例 2：**

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

**提示：**

*  树中节点数的范围在  \[ 0 , 1 0 5 \] \[0, 10^5\] \[0,105\] 内
 *   − 1000 < = N o d e . v a l < = 1000 -1000 <= Node.val <= 1000 −1000<=Node.val<=1000

### 简单递归解法 ###

这道题目和 [二叉树的最大深度][Link 1] 一样，都可以使用递归解法。

**求解公式为：** 二叉树的最小深度 =  M i n Min Min(左子树的最小深度，右子树的最小深度) + `1`。

但是需要注意的是，只有**左子树和右子树都不为空**的时候才能使用上述公式求解。

如果左子树为空，那么**二叉树的最小深度 = 右子树的最小深度 + 1**。如下图所示：  
![image.png][]  
同样的如果右子树为空，那么**二叉树的最小深度 = 左子树的最小深度 + 1**。

极端情况下会退化成链表，如下图所示：  
![image.png][image.png 1]

##### Java 代码实现 #####

##### Go 代码实现 #####

/**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func minDepth(root *TreeNode) int {
        
    
        if root == nil {
        
            return 0
        }
    
        if root.Left == nil && root.Right == nil {
        
            return 1
        }
    
        leftMin := minDepth(root.Left)
        rightMin := minDepth(root.Right)
    
        if root.Left == nil {
        
            return rightMin + 1
        }else if root.Right == nil {
        
            return leftMin + 1
        }else{
        
            return min(leftMin, rightMin) + 1
        }
    
    }
    
    func min(a int, b int) int {
        
        if a < b {
        
            return a
        }else {
        
            return b
        }
    }

##### 复杂度分析 #####

*  **时间复杂度**： O ( N ) O(N) O(N)，`N` 为二叉树中节点的个数，每个节点都需要计算一次，总共 `N` 次。
 *  **空间复杂度**： O ( N ) O(N) O(N)，`N` 为二叉树中节点的个数，空间复杂度为调用栈的深度，最多为 `N` ，即二叉树退化成链表的时候。

### DFS ###

相较于上一步的简单递归解法，深度优先遍历的优点是可以进行剪枝，如下图所示：  
![image.png][image.png 2]  
`root节点3` 到 `节点9` 的深度是`2`，那么在遍历到 `节点20` 的时候深度已经达到`2`了，后面就无需再遍历，可以直接返回了。

另外需要注意的是边界条件和还原现场：

*  **边界条件**：碰到叶子结点时计算一次最小深度，并返回。
 *  **还原现场**：`depth--`，每次回退到上一层的时候深度跟着要减一。

##### Java 代码实现 #####

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        private int depth = 1;
        private int ans = Integer.MAX_VALUE;
        public int minDepth(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }
            dfs(root);
            return ans; 
        }
    
        private void dfs(TreeNode node){
        
    
            // 剪枝
            if(depth >= ans){
        
                return;
            }
    
            // 边界条件，碰到叶子结点计算一次最小深度
            if(node.left == null && node.right == null){
        
                ans = Math.min(ans, depth);
                return;
            }
    
            depth++;
    
            // 遍历左子树
            if(node.left != null){
        
                dfs(node.left);
            }
            
            // 遍历右子树
            if(node.right != null){
        
                dfs(node.right);
            }
            
            // 还原现场
            depth--;
            
        }
    }

##### Go 代码实现 #####

/**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    
    var (
        depth int
        ans int
    )
    func minDepth(root *TreeNode) int {
        
    
        if root == nil {
        
            return 0
        }
    
        depth = 1
        ans = 2 << 32 - 1
    
        dfs(root)
        
        return ans
    
    }
    
    func dfs(node *TreeNode) {
        
        // 剪枝
        if depth >= ans {
        
            return
        }
    
        // 边界条件
        if node.Left == nil && node.Right == nil {
        
            ans = min(ans, depth)
            return
        }
    
        depth++
        if(node.Left != nil){
        
            dfs(node.Left)
        }
        if(node.Right != nil){
        
            dfs(node.Right)
        }
        // 还原现场
        depth--
    }
    
    func min(a int, b int) int {
        
        if a < b {
        
            return a
        }else {
        
            return b
        }
    }

##### 复杂度分析 #####

*  **时间复杂度**： O ( N ) O(N) O(N)，`N` 为二叉树中的节点个数，最差的情况是每个节点都需要遍历一次，总计 `N` 次。
 *  **空间复杂度**： O ( N ) O(N) O(N)，`N` 为二叉树中节点的个数，空间复杂度为调用栈的深度，最多为 `N` 层。

### BFS ###

广度优先遍历，一层一层的逐层遍历，遇到的第一个叶子结点的深度就是最小深度。

以下图为例，当遍历到 `节点9` 的时候，就可以直接返回了。  
![image.png][image.png 3]

##### Java 代码实现 #####

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public int minDepth(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            int depth = 1;
            queue.offer(root);
            while(!queue.isEmpty()){
        
                // 同一层节点个数
                int len = queue.size();
    
                // 将同一层节点全部取出，并将下一层节点入队
                for(int i = 0; i < len; i++){
        
                    TreeNode node = queue.poll();
                    // 第一次遇到叶子结点，就是最小深度
                    if(node.left == null && node.right == null){
        
                        return depth;
                    }
                    // 左子树入队
                    TreeNode leftNode = node.left;
                    if(leftNode != null){
        
                        queue.offer(leftNode);
                    }
    
                    // 右子树入队
                    TreeNode rightNode = node.right;
                    if(rightNode != null){
        
                        queue.offer(rightNode);
                    }
                }
                // 同一层节点全部取出后，深度加一
                depth++;
            }
            return depth; 
        }
    
    }

##### Go 代码实现 #####

/**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    
    
    func minDepth(root *TreeNode) int {
        
    
        if root == nil {
        
            return 0
        }
    
        queue := []*TreeNode{
        root}
        depth := 1
    
        for len(queue) > 0 {
        
            // 同一层节点个数
            len := len(queue)
            
            // 将同一层节点全部取出，并将下一层节点入队
            for i := 0; i < len; i++ {
        
                node := queue[0]
                queue = queue[1:]
                // 第一次遇到叶子结点，就是最小深度
                if node.Left == nil && node.Right == nil {
        
                    return depth
                }
                // 左子树入队
                if node.Left != nil {
        
                    queue = append(queue, node.Left)
                }
                // 右子树入队
                if node.Right != nil {
        
                    queue = append(queue, node.Right)
                }
            }
            // 同一层节点全部取出后，深度加一
            depth++
        }
    
    
        return depth
    }

##### 复杂度分析 #####

*  **时间复杂度**： O ( N ) O(N) O(N)，`N` 为二叉树中节点的个数，最坏的情况下需要遍历每一个节点。
 *  **空间复杂度**： O ( N ) O(N) O(N)，`N` 为二叉树中节点的个数，空间复杂度主要取决于队列的大小，最差的情况就是放 `N` 个元素。

### 总结 ###

**简单递归解法** 的思路最为简单，但是需要计算所有节点，所以效率上不是最好的。

**DFS** 和 **BFS** 虽然时间复杂度上也都是 O ( N ) O(N) O(N)，但这是在最坏的情况下得到的，通常都不需要遍历所有节点，所以效率要高一些。

因为 **BFS** 比 **DFS** 所需要遍历的节点数会更少一些，所以个人觉得求最小深度（最短路径）的题目使用 **BFS** 更为合适一些。

[8550e78685022eb28bf1dac398fa1060.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/38c3a63a788d4a909814279a75bdec10.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzU1OTYwMjk1OQ==&mid=2247487549&idx=1&sn=053b9811f47fbbfc6f6f63ecad890bf6&chksm=fc159c5dcb62154bf9889064e18c0af6e62c583bdb7b7ca2edb3516c9812fd404c24ec21b447#rd
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/e97a9e5f75104e10846e8bdfda23e7c1.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/e6372f057ad143e88efa383f4d7ed3d3.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/bdf7f1bb9522458a8a0c48465ac5dfb3.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/b304de8764d8476fb439428f6720ef40.png