LeetCode算法题-Diameter of Binary Tree(Java实现)
这是悦乐书的第257次升级,第270篇原创
01 看题和准备
今天详情的是LeetCode算法题中Easy级别的第124题(顺位题号是543)。给定二叉树,您需要计算树的直径长度。 二叉树的直径是树中任意两个节点之间最长路径的长度。 此路径可能会也可能不会通过根节点。例:
给出一棵二叉树
1 / \ 2 3 / \4 5返回3,这是路径[4,2,1,3]或者[5,2,1,3]的长度。
注意:两个节点之间的路径长度由它们之间的边数表示。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 解题
题目要求是求二叉树的直径,根据题目给的示例,也可以了解成从根节点开始,左子树的深度与右子树的深度之和,但是题目又说了,也可能不经过根节点,所以我们需要求两者的最大值。计算任意一个节点的最长路径值,在其中取出最大值就可。递归方法的主体,和求二叉树最大深度的代码一样,只是中间加了一步取最大值的操作而已。
此解法的时间复杂度是O(n),空间复杂度是O(n)。
public int diameterOfBinaryTree(TreeNode root) { helper(root); return max;}private int max = 0;public int helper(TreeNode root) { if (root == null) { return 0; } int left = helper(root.left); int right = helper(root.right); max = Math.max(max, left+right); return Math.max(left, right)+1;}03 小结
算法专题目前已日更超过三个月,算法题文章124+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是一律内容,假如大家有什么好的解法思路、建议或者者其余问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!
说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode算法题-Diameter of Binary Tree(Java实现)
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode算法题-Diameter of Binary Tree(Java实现)