[Leetcode][第111题][JAVA][BFS][二叉树的最小深度][BFS][递归]

谁借莪１个温暖的怀抱￠ 2023-03-02 07:57 118阅读 0赞

#### 【问题描述】\[简单\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 递归 ######

自下而上  
**基本情况/结束条件 ：**  
叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点  
当 root 节点左右孩子都为空时，返回 1  
当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度  
当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值

**递推关系：遍历二叉树**

**复杂度**  
![在这里插入图片描述][20200728145722226.png]

class Solution { 
        public int minDepth(TreeNode root) { 
            if(root == null) return 0;
            //这道题递归条件里分为三种情况
            //1.左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可
            if(root.left == null && root.right == null) return 1;
            //2.如果左孩子和由孩子其中一个为空，那么需要返回比较大的那个孩子的深度 
            int m1 = minDepth(root.left);
            int m2 = minDepth(root.right);
            //这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;
            if(root.left == null || root.right == null) return m1 + m2 + 1;
            
            //3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可
            return Math.min(m1,m2) + 1; 
        }
    }

代码可以进行简化，当左右孩子为空时 m1和 m2 都为 0，可以和情况 2 进行合并，即返回 m1+m2+1

class Solution { 
        public int minDepth(TreeNode root) { 
            if(root == null) return 0;
            int m1 = minDepth(root.left);
            int m2 = minDepth(root.right);
            //1.如果左孩子和右孩子有为空的情况，直接返回m1+m2+1
            //2.如果都不为空，返回较小深度+1
            return root.left == null || root.right == null ? m1 + m2 + 1 : Math.min(m1,m2) + 1;
        }
    }

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

###### 2. BFS广度优先遍历 ######

一个优化的方法是利用广度优先搜索，我们按照树的层去迭代，第一个访问到的叶子就是最小深度的节点，这样就不用遍历所有的节点了。  
1.特判  
2.root入队 ，左右节点非空入队  
3.找到第一个左右节点均为空的节点即是答案

**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][20200827104038896.png_pic_center]

public int minDepth(TreeNode root) { 
            if (root == null)
                return 0;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);//入队
            int level = 0;
            while (!queue.isEmpty()) { //队列不为空就继续循环
                level++;
                int levelCount = queue.size();
                for (int j = 0; j < levelCount; j++) { 
                    TreeNode node = queue.poll();//出队
                    //如果当前node节点的左右子树都为空，直接返回level即可
                    if (node.left == null && node.right == null)
                        return level;
                    if (node.left != null)
                        queue.add(node.left);
                    if (node.right != null)
                        queue.add(node.right);
                }
            }
            return -1;
        }

#### 【总结】 ####

###### 1. 相关题目 ######

[\[Leetcode\]\[第104题\]\[JAVA\]\[二叉树的最大深度\]\[递归\]\[BFS\]][Leetcode_104_JAVA_BFS]

###### 2.递归 ######

在实现递归函数之前，有两件重要的事情需要弄清楚:

递推关系：一个问题的结果与其子问题的结果之间的关系。  
基本情况：不需要进一步的递归调用就可以直接计算答案的情况。可理解为递归跳出条件。  
一旦我们计算出以上两个元素，再想要实现一个递归函数，就只需要根据递推关系调用函数本身，直到其抵达基本情况。

###### 3.递归模板套路 ######

递归模板套路  
由下到上  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

有上到下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
区别  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]

参考链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/li-jie-zhe-dao-ti-de-jie-shu-tiao-jian-by-user7208/  
参考链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/java-di-gui-he-fei-di-gui-liang-chong-fang-shi-de-/  
递归学习资料：https://leetcode-cn.com/circle/article/koSrVI/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230208/7ae7bca4fa58485b8f6ce05837926869.png
[20200728145722226.png]: /images/20230208/c6d4e51055074d489e9e92ca11e4a1ec.png
[20200827104038896.png_pic_center]: /images/20230208/8c2e32aa106645fb86b06a3deeb38925.png
[Leetcode_104_JAVA_BFS]: https://blog.csdn.net/dadongwudi/article/details/107633240
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230208/e4124b32f41442d4b6415f57090c00c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20230208/101420bce7e349028b03549591615836.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: /images/20230208/6072f0c9b3b14b8c88b2e691e98018b2.png