这是悦乐书的第 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 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/85d80eb85418