【亡羊补牢】挑战数据结构与算法 第54期 LeetCode 543. 二叉树的直径(二叉树)
发布日期:2021-06-29 14:34:33
浏览次数:2
分类:技术文章
本文共 1161 字,大约阅读时间需要 3 分钟。
仰望星空的人,不应该被嘲笑
题目描述
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意:两结点之间的路径长度是以它们之间边的数目表示。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/diameter-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。解题思路
通过后序遍历,每一次返回当前根节点下的左右孩子的深度最大值,然后每一次递归求一下左右孩子路径和的最大值即可。
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {number} */var diameterOfBinaryTree = function (root) { if (!root) return 0; let res = 0; let dfs = (root) => { if (!root) return 0; // 后序遍历 先遍历左孩子 let left = root.left && dfs(root.left) + 1; let right = root.right && dfs(root.right) + 1; // 每次求直径,比较左右孩子路径和的最大值 res = Math.max(left + right, res); // 递归时候返回左右孩子深度最长 return Math.max(left, right) } dfs(root); return res;};
最后
文章产出不易,还望各位小伙伴们支持一波!
往期精选:
小伙伴们可以在Issues中提交自己的解题代码,🤝 欢迎Contributing,可打卡刷题,Give a ⭐️ if this project helped you!
,方便小伙伴阅读玩耍~
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/108848895 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月25日 16时46分19秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
爬取小说——主体部分
2019-04-29
Python 窗口化操作
2019-04-29
excel的常用函数(二)
2019-04-29
excel的逻辑函数
2019-04-29
excel文本函数
2019-04-29
excel时间日期函数
2019-04-29
excel查找引用函数
2019-04-29
棱镜门事件
2019-04-29
拼多多远程删除用户照片事件
2019-04-29
power BI desktop
2019-04-29
中国信息化发展八大趋势(一)
2019-04-29
中国信息化发展八大趋势(二)
2019-04-29
中国信息化发展八大趋势(三)
2019-04-29
中国信息化发展八大趋势(四)
2019-04-29
电商大战二十年
2019-04-29
神奇的麦考林
2019-04-29
centos7使用rpm安装mysql遇到的error: Failed dependencies: mysql-community-common(x86-64) 5.7.9 is needed
2019-04-29
spark报错:warn util.utils::service ‘sparkUI‘ can not bind on part 4040.Attempting port 4041.4042等错误
2019-04-29