LeetCode 111.二叉树的最小深度
题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5提示：
- 树中节点数的范围在
[0, 10^5]内 -1000 <= Node.val <= 1000
思路
首先要注意到本题中最小深度的定义：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是这里是叶子节点，即左右孩子均为空的节点。
本题笔者选择使用递归法来解决。
递归三部曲：
- 确定递归函数的参数和返回值。参数为要传入的二叉树根节点，返回的是int类型的深度。
- 确定终止条件。终止条件是遇到空节点返回0，表示当前节点的高度为0。
- 确定单层递归的逻辑。如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。如果右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。如果左右子树都不为空，返回左右子树深度最小值 + 1 。
代码
C++版：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 递归法，后序遍历
int getHeight(TreeNode* node){
if(node==NULL) return 0;
int leftHeight=getHeight(node->left); // 左
int rightHeight=getHeight(node->right); // 右
// 中
if(node->left==NULL && node->right!=NULL){
return rightHeight+1;
}
if(node->left!=NULL && node->right==NULL){
return leftHeight+1;
}
return min(leftHeight,rightHeight)+1;
}
int minDepth(TreeNode* root) {
return getHeight(root);
}
};Python版：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
# 递归法，后序遍历
def getHeight(self, node):
if node is None:
return 0
leftHeight = self.getHeight(node.left) # 左
rightHeight = self.getHeight(node.right) # 右
# 当一个左子树为空，右不为空，这时并不是最低点
if node.left is None and node.right is not None:
return 1 + rightHeight
# 当一个右子树为空，左不为空，这时并不是最低点
if node.left is not None and node.right is None:
return 1 + leftHeight
result = 1 + min(leftHeight, rightHeight)
return result
def minDepth(self, root: Optional[TreeNode]) -> int:
return self.getHeight(root)
需要注意的地方
1.求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
2.注意一种特殊的情况：根节点的左子树为空，而右子树不为空，如果使用【104.二叉树的最大深度】中对中节点的处理方法height=1+min(leftHeight,rightHeight)则会得到错误的最小深度1。
原文地址：https://blog.csdn.net/weixin_50878507/article/details/143103739
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！