朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第104道二叉树OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!
数据结构与算法专栏:数据结构与算法
个 人 主 页 :stackY、
C 语 言 专 栏:C语言:从入门到精通
LeetCode--104.二叉树的最大深度:https://leetcode.cn/problems/maximum-depth-of-binary-tree/
目录
1.题目介绍
2.实例演示
3.解题思路
代码演示:
递归展开图:
1.题目介绍
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
2.实例演示
3.解题思路
要求二叉树的最大深度,我们同样的也是采用递归遍历的方法:
二叉树的最大深度等价于:左右子树的最大深度 + 1
要求1的高度,那么就得求它的左右子树2、3的高度,要求2和3的高度就得分别求它们左右子树的高度...依次类推,4的左右子树高度为0,这时4返回给2时返回的高度为0+1(0表示它的左右子树的高度为0,1表示它自己的高度为1),也就是说再返回时要加上自己本身的高度,所以2的左子树的高度为1,再来计算2的右子树5的高度,计算5的高度又得计算5的左右子树的高度,5的左子树高度为1,右子树高度为0,取较大的为1,5返回2时再加上自己本身的高度为2,所以取2的左右子树较高的高度为2,所以2返回1时再加上自己本身的高度为3.....依次类推,直到遍历完整个二叉树。所以最后整颗树的高度为4。
代码演示:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /* 解题思路: 二叉树的最大深度等价于:左右子树的最大深度 + 1 */ int maxDepth(struct TreeNode* root){ //为空树就返回0 if(root == NULL) return 0; //计算左右子树的深度 int High_Left = maxDepth(root->left) + 1; int High_Right = maxDepth(root->right) + 1; //比较左右子树的大小,返回最大的深度 if(High_Left > High_Right) { return High_Left; } return High_Right; }
递归展开图:
每一次递归的返回值并不是直接返回到最外面,而是返回上一层,这一点要注意。文章来源:https://www.toymoban.com/news/detail-512508.html
朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持! 文章来源地址https://www.toymoban.com/news/detail-512508.html
到了这里,关于二叉树OJ题:LeetCode--104.二叉树的最大深度的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!