深圳布吉网站建设,3d全景网站怎么做,php网站模板带后台,网站是怎么做的111.二叉树的最小深度
111. 二叉树的最小深度 - 力扣#xff08;LeetCode#xff09;https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
题目描述#xff1a;
给定一个二叉树#xff0c;找出其最小深度。
最小深度是从根节点到最近叶子节点的最…111.二叉树的最小深度
111. 二叉树的最小深度 - 力扣LeetCodehttps://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
题目描述
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明叶子节点是指没有子节点的节点。
示例 1 输入root [3,9,20,null,null,15,7]
输出2示例 2
输入root [2,null,3,null,4,null,5,null,6]
输出5
题目分析
按照上一篇文章中所写的求二叉树的最大深度对的解法这道题应该不难。
后序递归解法
采用比较容易理解的后续递归及递归三部曲可以得到如下代码
1. 递归第一步确定递归函数的参数和返回值
参数为要传入的二叉树根节点返回的是int类型的深度。
代码如下
int getDepth(TreeNode* node)2. 递归第二步确定终止条件
终止条件也是遇到空节点返回0表示当前节点的高度为0。
代码如下
if (node NULL) return 0;3. 递归第三步确定单层递归的逻辑
这块和求最大深度可就不一样了一些同学可能会写如下代码
int leftDepth getDepth(node-left);
int rightDepth getDepth(node-right);
int result 1 min(leftDepth, rightDepth); //关键问题出在这一步
return result; 对于左右子树均存在时上述代码没有问题。但是当子树不存在时由前两步getDepth得到的深度会存在0如下图所示 回顾一下题目所给的最小深度的定义
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是到最近的叶子节点即没有左右子节点的叶子节点。
那么刚刚所写的单层递归逻辑的代码中是没有判断是否为叶子节点的功能的
int leftDepth getDepth(node-left);
int rightDepth getDepth(node-right);
int result 1 min(leftDepth, rightDepth); //关键问题出在这一步
return result;
补救措施就是在得到leftDepth和rightDepth之后要判断一下左右子树的存在情况。
如果左子树为空右子树不为空说明最小深度是 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);}
};
上述代码是写了一个专门的getDepth函数进行递归也可以不写直接在力扣提供的函数minDepth上进行递归如下所示
class Solution {
public:int minDepth(TreeNode* root) {if(root nullptr) return 0;//左int leftDepth minDepth(root-left);//右int rightDepth minDepth(root-right);if(root-left nullptr root-right ! nullptr) return rightDepth 1;if(root-left ! nullptr root-right nullptr)return leftDepth 1;int result min(leftDepth, rightDepth) 1;return result;}
};
注意上面两个写法中的result min(leftDepth, rightDepth) 1; 这行代码即包含了左右子树均存在的情况还包含了左右子树均不存在的情况。均存在时就去最小值加1均不存在时leftDepth和rightDepth均为0那么算上此时两个空子树的父节点那一层result做了加1操作可以想象整个二叉树只有一个根节点组成时的情形。
所以代码里的1操作就是在后序遍历中处理完了左右子树后开始考虑子树对应的根节点计算深度左右中。 层序遍历解法
在二叉树层序遍历文章的基础上来实现最小深度的求解关键一点就是第一次遍历到某个节点的左右孩子都为空的时候说明遍历到最低点了此时应该直接return depth程序运行结束。如果其中一个孩子不为空则不是最低点。
代码如下
class Solution {
public://层序遍历int minDepth(TreeNode* root) {if(root nullptr) return 0;queueTreeNode* que;que.push(root);int depth 0;while(!que.empty()){int size que.size();depth;for(int i 0; i size; i){TreeNode* node que.front();que.pop();//最低处判断放这里也行// if(node-left nullptr node-right nullptr)// return depth;if(node-left) que.push(node-left);if(node-right) que.push(node-right);if(node-left nullptr node-right nullptr)return depth; }}return depth;}
};
