二叉树OJ题:LeetCode--104.二叉树的最大深度

这篇具有很好参考价值的文章主要介绍了二叉树OJ题:LeetCode--104.二叉树的最大深度。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第104道二叉树OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!

数据结构与算法专栏:数据结构与算法

个  人  主  页 :stackY、

C 语 言 专 栏C语言:从入门到精通

二叉树OJ题:LeetCode--104.二叉树的最大深度

 LeetCode--104.二叉树的最大深度:https://leetcode.cn/problems/maximum-depth-of-binary-tree/

目录

1.题目介绍

2.实例演示

3.解题思路

代码演示:

递归展开图:


1.题目介绍

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

二叉树OJ题:LeetCode--104.二叉树的最大深度

2.实例演示

二叉树OJ题:LeetCode--104.二叉树的最大深度

3.解题思路

要求二叉树的最大深度,我们同样的也是采用递归遍历的方法:

二叉树的最大深度等价于:左右子树的最大深度 + 1

二叉树OJ题:LeetCode--104.二叉树的最大深度

要求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;
}

 递归展开图:

二叉树OJ题:LeetCode--104.二叉树的最大深度

 每一次递归的返回值并不是直接返回到最外面,而是返回上一层,这一点要注意。

朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!  文章来源地址https://www.toymoban.com/news/detail-512508.html

到了这里,关于二叉树OJ题:LeetCode--104.二叉树的最大深度的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包