手机网站设计需要学什么,工作报告是组织进行沟通的有效渠道,西安的推广公司,中国建设规划采购网站#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 二叉树的最大深度二叉树的最… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 二叉树的最大深度二叉树的最小深度完全二叉树的节点个数总结 先看第一题求二叉树的最大深度
二叉树的最大深度
104. 二叉树的最大深度 - 力扣LeetCode
这道题的思路主要有两种第一种是正常求解二叉树的最大深度即从上至下搜索二叉树最大深度的定义是从根节点到叶子节点的最远距离为二叉树的最大深度。我们可以按照前序遍历的方法向下遍历依次统计出到叶子结点的距离取最大值即可。
第二种思路是由于二叉树的最大高度就是二叉树的最大深度所以可以采用求二叉树最大高度的方法求解出本题高度是逐渐变小的从根节点到叶子节点这是它和直接求深度的本质区别这个时候我们可以以后序遍历的方法来从上到下求取最大高度完成求解。
先给出正常逻辑求深度的代码
class Solution {
public:
int result0;
void dfs(TreeNode*root,int deepth){resultresultdeepth?result:deepth;if(root-left)dfs(root-left,deepth1);if(root-right)dfs(root-right,deepth1);}int maxDepth(TreeNode* root) {if(rootNULL)return 0;dfs(root,1);return result;}
};下面的是以求高度的思路写出的代码
class Solution {
public:int maxDepth(TreeNode* root) {if(rootnullptr){return 0;}int leftvalmaxDepth(root-left);int rightvalmaxDepth(root-right);int max11max(leftval,rightval);return max1;}
};两种思路中我更偏向于按照深度的思路这种思路我觉得更利于理解。
二叉树的最小深度
111. 二叉树的最小深度 - 力扣LeetCode
这道题是求解二叉树的最小深度如果按照直接求深度的思想写代码思路相差的并不多。只有一点需要注意并不是直接取deepth和result中的最小值因为那样直接去取最小值会出现当根节点一开始左子树或右子树有一个没有的情况时会直接使result附上结果为1的答案但是实际上这与二叉树的深度定义本身是不相符合的深度的定义是根节点到叶子结点的距离所以一定要遍历到叶子节点时才能算是一个答案具体代码看下面。
class Solution {
public:int resultINT_MAX;void dfs(TreeNode* root,int deepth){if(root-leftnullptrroot-rightnullptr){resultresultdeepth?result:deepth;}if(root-left){dfs(root-left,deepth1);}if(root-right){dfs(root-right,deepth1);}}int minDepth(TreeNode* root) {if(rootnullptr){return 0;}dfs(root,1);return result;}
};上面的代码已经很清晰的写出了求解最小深度的代码当该节点的左右节点都为空时候那么该节点才是叶子节点这时候我们再收获答案进行比较。第二种思路在这里就不给出了和这种思路差不太多但是本人认为使用高度来求深度应用在这道题中稍显麻烦了一些。
完全二叉树的节点个数
222. 完全二叉树的节点个数 - 力扣LeetCode
这道题也分成两种大致的思路一种是按照正常思路解即不管他是什么类型的二叉树直接将所有节点全遍历一次记录下一共遍历了几个节点后返回答案这样的思路无论是什么二叉树都能遍历出来属于暴力解法。这里不给出代码。
第二种思路就是按照满二叉树的解法满二叉树一定是完全二叉树由于完全二叉树中一定会有某子树是完全二叉树我们按照这样的性质来遍历判断从根节点开始的各个子树是否满足满二叉树的特点来求解这样的好处是可以减少遍历一部分的中间节点但是值得注意的是时间复杂度貌似和暴力求解差不多都是On。
class Solution {
public:int countNodes(TreeNode* root) {if(rootnullptr){return 0;}TreeNode* leftroot-left;int leftval0,rightval0;TreeNode* rightroot-right;while(left){leftleft-left;leftval;}while(right){rightright-right;rightval;}if(leftvalrightval){return (2leftval)-1;}return countNodes(root-left)countNodes(root-right)1;}
}代码绝大部分是结束判断语句判断从某节点起始它的子树是否为完全二叉树因为如果是的话从该节点的两侧开始遍历如果节点数目相等那么肯定就是完全二叉树按照这样的思路即可完成判断。判断成功了返回的是当前完全二叉树共多少节点。这个代码不需要担心如果有单独节点出现因为单独节点没有左右子树也可以看作为完全二叉树
总结
今天我们完成了二叉树的最大深度、二叉树的最小深度、完全二叉树的节点个数三道题相关的思想需要多复习回顾。接下来我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
