discuz wordpress主题,天津谷歌优化公司,平面广告设计主题,北京++网站建设咨询顾问公司力扣题目链接(opens new window)
给定一个二叉树#xff0c;找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7], 返回它的最小深度 2
思路
看完了这篇104.二…
力扣题目链接(opens new window)
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7], 返回它的最小深度 2
思路
看完了这篇104.二叉树的最大深度 (opens new window)再来看看如何求最小深度。
直觉上好像和求最大深度差不多其实还是差不少的。
本题依然是前序遍历和后序遍历都可以前序求的是深度后序求的是高度。
二叉树节点的深度指从根节点到该节点的最长简单路径边的条数或者节点数取决于深度从0开始还是从1开始二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数后者节点数取决于高度从0开始还是从1开始
那么使用后序遍历其实求的是根节点到叶子节点的最小距离就是求高度的过程不过这个最小距离 也同样是最小深度。
以下讲解中遍历顺序上依然采用后序遍历因为要比较递归返回之后的结果本文我也给出前序遍历的写法。
本题还有一个误区在处理节点的过程中最大深度很容易理解最小深度就不那么好理解如图 这就重新审题了题目中说的是最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。
什么是叶子节点左右孩子都为空的节点才是叶子节点
#递归法
来来来一起递归三部曲
确定递归函数的参数和返回值
参数为要传入的二叉树根节点返回的是int类型的深度。
代码如下
int getDepth(TreeNode* node)确定终止条件
终止条件也是遇到空节点返回0表示当前节点的高度为0。
代码如下
if (node NULL) return 0;确定单层递归的逻辑
这块和求最大深度可就不一样了一些同学可能会写如下代码
int leftDepth getDepth(node-left);
int rightDepth getDepth(node-right);
int result 1 min(leftDepth, rightDepth);
return result;这个代码就犯了此图中的误区 如果这么求的话没有左孩子的分支会算为最短深度。
所以如果左子树为空右子树不为空说明最小深度是 1 右子树的深度。
反之右子树为空左子树不为空最小深度是 1 左子树的深度。 最后如果左右子树都不为空返回左右子树深度最小值 1 。
代码如下
int leftDepth getDepth(node-left); // 左
int rightDepth getDepth(node-right); // 右// 中
// 当一个左子树为空右不为空这时并不是最低点
if (node-left NULL node-right ! NULL) { return 1 rightDepth;
}
// 当一个右子树为空左不为空这时并不是最低点
if (node-left ! NULL node-right NULL) { return 1 leftDepth;
}
int result 1 min(leftDepth, rightDepth);
return result;遍历的顺序为后序左右中可以看出求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
整体递归代码如下
class Solution {
public:int getDepth(TreeNode* node) {if (node NULL) return 0;int leftDepth getDepth(node-left); // 左int rightDepth getDepth(node-right); // 右// 中// 当一个左子树为空右不为空这时并不是最低点if (node-left NULL node-right ! NULL) { return 1 rightDepth;} // 当一个右子树为空左不为空这时并不是最低点if (node-left ! NULL node-right NULL) { return 1 leftDepth;}int result 1 min(leftDepth, rightDepth);return result;}int minDepth(TreeNode* root) {return getDepth(root);}
};精简之后代码如下
class Solution {
public:int minDepth(TreeNode* root) {if (root NULL) return 0;if (root-left NULL root-right ! NULL) {return 1 minDepth(root-right);}if (root-left ! NULL root-right NULL) {return 1 minDepth(root-left);}return 1 min(minDepth(root-left), minDepth(root-right));}
};精简之后的代码根本看不出是哪种遍历方式所以依然还要强调一波如果对二叉树的操作还不熟练尽量不要直接照着精简代码来学。
前序遍历的方式
class Solution {
private:int result;void getdepth(TreeNode* node, int depth) {// 函数递归终止条件if (node nullptr) {return;}// 中处理逻辑判断是不是叶子结点if (node - left nullptr node-right nullptr) {result min(result, depth);}if (node-left) { // 左getdepth(node-left, depth 1);}if (node-right) { // 右getdepth(node-right, depth 1);}return ;}public:int minDepth(TreeNode* root) {if (root nullptr) {return 0;}result INT_MAX;getdepth(root, 1);return result;}
};#迭代法
相对于104.二叉树的最大深度 (opens new window)本题还可以使用层序遍历的方式来解决思路是一样的。
如果对层序遍历还不清楚的话可以看这篇二叉树层序遍历登场(opens new window)
需要注意的是只有当左右孩子都为空的时候才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点
代码如下详细注释
class Solution {
public:int minDepth(TreeNode* root) {if (root NULL) return 0;int depth 0;queueTreeNode* que;que.push(root);while(!que.empty()) {int size que.size();depth; // 记录最小深度for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (node-left) que.push(node-left);if (node-right) que.push(node-right);if (!node-left !node-right) { // 当左右孩子都为空的时候说明是最低点的一层了退出return depth;}}}return depth;}
};
