LeetCode 111.二叉树的最小深度

标题形貌

给定一个二叉树，找出其最小深度。
最小深度是从根节点到近来叶子节点的最短路径上的节点数目。
分析：叶子节点是指没有子节点的节点。
示例 1：

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

复制代码

示例 2：

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

复制代码

提示：

• 树中节点数的范围在 [0, 10^5] 内
  
• -1000 <= Node.val <= 1000
  

思绪

起首要注意到本题中最小深度的界说：最小深度是从根节点到近来叶子节点的最短路径上的节点数目。注意是这里是叶子节点，即左右孩子均为空的节点。
本题笔者选择利用递归法来办理。
递归三部曲：

• 确定递归函数的参数和返回值。参数为要传入的二叉树根节点，返回的是int范例的深度。
  
• 确定制止条件。制止条件是遇到空节点返回0，表现当前节点的高度为0。
  
• 确定单层递归的逻辑。如果左子树为空，右子树不为空，分析最小深度是 1 + 右子树的深度。如果右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。如果左右子树都不为空，返回左右子树深度最小值 + 1 。
  

代码

C++版：

2. /**
3. * Definition for a binary tree node.
4. * struct TreeNode {
5. *     int val;
6. *     TreeNode *left;
7. *     TreeNode *right;
8. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11. * };
12. */
13. class Solution {
14. public:
15.     // 递归法，后序遍历
16.     int getHeight(TreeNode* node){
17.         if(node==NULL) return 0;
18.         int leftHeight=getHeight(node->left); // 左
19.         int rightHeight=getHeight(node->right); // 右
20.         // 中
21.         if(node->left==NULL && node->right!=NULL){
22.             return rightHeight+1;
23.         }   
24.         if(node->left!=NULL && node->right==NULL){
25.             return leftHeight+1;
26.         }
27.         return min(leftHeight,rightHeight)+1;
28.     }
29.     int minDepth(TreeNode* root) {
30.         return getHeight(root);
31.     }
32. };

复制代码

Python版：

2. # Definition for a binary tree node.
3. # class TreeNode:
4. #     def __init__(self, val=0, left=None, right=None):
5. #         self.val = val
6. #         self.left = left
7. #         self.right = right
8. class Solution:
9.     # 递归法，后序遍历
10.     def getHeight(self, node):
11.         if node is None:
12.             return 0
13.         leftHeight = self.getHeight(node.left)  # 左
14.         rightHeight = self.getHeight(node.right)  # 右
15.         
16.         # 当一个左子树为空，右不为空，这时并不是最低点
17.         if node.left is None and node.right is not None:
18.             return 1 + rightHeight
19.         
20.         # 当一个右子树为空，左不为空，这时并不是最低点
21.         if node.left is not None and node.right is None:
22.             return 1 + leftHeight
23.         
24.         result = 1 + min(leftHeight, rightHeight)
25.         return result
27.     def minDepth(self, root: Optional[TreeNode]) -> int:
28.         return self.getHeight(root)
29.         

复制代码

必要注意的地方

1.求二叉树的最小深度和求二叉树的最大深度的差异重要在于处理处罚左右孩子不为空的逻辑。
2.注意一种特殊的情况：根节点的左子树为空，而右子树不为空，如果利用【104.二叉树的最大深度】中对中节点的处理处罚方法height=1+min(leftHeight,rightHeight)则会得到错误的最小深度1。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告