首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode题组:第543题-二叉树的直径

LeetCode题组:第543题-二叉树的直径

作者头像
K同学啊
发布于 2020-04-10 08:24:12
发布于 2020-04-10 08:24:12
39900
代码可运行
举报
运行总次数:0
代码可运行

1.题目

难度:简单

给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :

给定二叉树

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
      1
     / \
    2   3
   / \     
  4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。


2.我的解答

把问题分解为: 直径 = max{目前最大直径,左子树深度 + 右子树深度}

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int max (int a,int b) {
    return a > b ? a : b;
}
int travelTree(struct TreeNode * root, int * diameter) {
    if (root == NULL) {
        return 0;
    }
    int left = travelTree(root->left, diameter);
    int right = travelTree(root->right, diameter);
    *diameter = max(*diameter, left + right);
    return 1 + max(left, right);
}

int diameterOfBinaryTree(struct TreeNode* root){
    int diameter = 0;
    travelTree(root, &diameter);
    return diameter;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/04/09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
​LeetCode刷题实战543:二叉树的直径
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2022/04/12
2420
​LeetCode刷题实战543:二叉树的直径
LeetCode-543-二叉树的直径
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
benym
2022/07/14
2420
LeetCode 543. 二叉树的直径(DFS)
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
Michael阿明
2020/07/13
4760
LeetCode 543. 二叉树的直径(DFS)
【leetcode刷题】T142-二叉树的直径
https://leetcode-cn.com/problems/diameter-of-binary-tree/
木又AI帮
2019/08/19
4210
【每日leetcode】25.二叉树的直径
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 注意:两结点之间的路径长度是以它们之间边的数目表示。
一条coding
2021/08/12
4830
二叉树的直径(LeetCode 543)
二叉树的 直径 是指树中任意两个节点之间最长路径的长度 。这条路径可能经过也可能不经过根节点 root 。
恋喵大鲤鱼
2024/01/20
1740
二叉树的直径(LeetCode 543)
二叉树问题(四)-LeetCode 502、543、637、606、114、979(最大堆,IPO)
假设 力扣(LeetCode)即将开始其 IPO。为了以更高的价格将股票卖给风险投资公司,力扣 希望在 IPO 之前开展一些项目以增加其资本。由于资源有限,它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。 给定若干个项目。对于每个项目 i,它都有一个纯利润 Pi,并且需要最小的资本 Ci 来启动相应的项目。最初,你有 W 资本。当你完成一个项目时,你将获得纯利润,且利润将被添加到你的总资本中。 总而言之,从给定项目中选择最多 k 个不同项目的列表,以最大化最终资本,并输出最终可获得的最多资本。
算法工程师之路
2019/12/24
5360
【Leetcode -404.左子叶之和 -543.二叉树的直径】
输入: root = [3, 9, 20, null, null, 15, 7] 输出 : 24 解释 : 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
YoungMLet
2024/03/01
1020
【Leetcode -404.左子叶之和 -543.二叉树的直径】
[Leetcode][python]二叉树的直径
https://leetcode-cn.com/problems/diameter-of-binary-tree/description/
蛮三刀酱
2019/03/26
9020
图解LeetCode——543. 二叉树的直径
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
爪哇缪斯
2023/05/31
8610
图解LeetCode——543. 二叉树的直径
LeetCode 平衡二叉树(二叉树)
给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为:
SakuraTears
2022/01/13
3810
LeetCode 平衡二叉树(二叉树)
Leetcode No.110 平衡二叉树
示例 1: 输入:root = [3,9,20,null,null,15,7] 输出:true
week
2021/05/06
2840
【LeetCode热题100】【二叉树】二叉树的直径
要找两个节点之间最多的边数,这个最多的边数必定是某个节点的左右子树的深度之和,因此递归计算每个子树的深度,过程中记录最大和即可
叶茂林
2024/04/10
1140
由浅入深二叉树刷题指南与讲解
上一篇我们已经了解了二叉树的实现方式, 那么本篇重在进入二叉树OJ刷题环节, 我也会分享我在写题的思路, 帮助我们更好的理解二叉树, 并且本篇也进行二叉树其他方法的实现, 也欢迎不同观点评论区留言.
用户11317877
2024/10/16
1080
由浅入深二叉树刷题指南与讲解
二叉树专项练习
主要是分治思想,大事化小,把其化成带有根节点的A A的左子树,A的右子树 ,再分别判断左子树与右子树的最大深度, 取两者最大值+1即二叉树的最大深度
lovevivi
2022/11/10
1930
二叉树专项练习
相同的树 单值二叉树 二叉树的最大深度
输入:p = [1,2,3], q = [1,2,3] 输出:true 示例 2:
南桥
2024/01/26
1170
相同的树 单值二叉树 二叉树的最大深度
【Leetcode】二叉树的最小深度
这题和【LeetCode】二叉树的最大深度很相似,我都是采用递归求解(流下了菜鸡的泪水)。我一开始撸出来的代码WA啦,[1,2]这个测试用例,我输出的最小深度是1,而答案说预期输出结果应该是2。因为根据题目描述“最小深度是从根结点到最近叶子结点的最短路径上的结点数量”,除非是只有一个根结点,否则必须要有一个叶子结点与根结点相连才能组成路径,所以[1,2]最小深度是2,[1]最小深度是1。 只有当左右子树同时存在时 才返回(1+左右子树中的最小深度),否则返回(不为空的那棵子树的深度+1)。
喜欢ctrl的cxk
2019/11/07
4500
【LeetCode-二叉树训练】
思路:通过root与其两个子节点判断是否相等,为了通过这个步骤遍历树的所有节点,采用递归方式去遍历即可
每天都要进步呀
2023/03/28
1840
【LeetCode-二叉树训练】
【初阶数据结构篇】二叉树算法题
本题如换做中序和后序遍历,直接调换插入数据顺序即可,其它思路都一样 中序遍历题目 后序遍历题目
半截诗
2024/10/09
1430
【初阶数据结构篇】二叉树算法题
二叉树:二叉树的直径
二叉树直径的定义:二叉树中路径的最大长度 二叉树中路径的最大长度,可以理解所有节点的左右子树高度之和的最大值。假设二叉树有n个节点,编号为{a1,a2,…,an}, 其对应的左右子树的高度之和为H = {h1,h2,h3,…,hn}, 则该二叉树的直径为max(H)。
lexingsen
2022/02/24
7900
相关推荐
​LeetCode刷题实战543:二叉树的直径
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档