来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diameter-of-binary-tree/
题目描述
给定一棵二叉树，计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
题目分析
如图二叉树：直径应该为3，长度路径：[10,1,2,3] 或 [10,1,2,9]。
任意一条路径都可看作由某个节点（比如节点 1 ）为起点，从其左子树和右子树向下遍历的路径拼接得到。
此时，问题就转化为：求节点的左右子树的深度之和的最大值。
【求二叉树的最大深度：https://www.jianshu.com/p/4617e07db87b】
代码实现（深度优先搜索）
public class ZhiJin543 {
public static void main(String[] args) {
ZhiJin543 zhiJin543 = new ZhiJin543();
/**
* 1
* 10 2
* 3 9
*/
TreeNode root = new TreeNode(1, new TreeNode(10), new TreeNode(2, new TreeNode(3), new TreeNode(9)));
zhiJin543.diameterOfBinaryTree(root);
}
int result = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
System.out.println("result=" + result);
return result;
}
/**
* 节点深度
*
* @param root
* @return
*/
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = depth(root.left);
int rightDepth = depth(root.right);
int zhiJin = leftDepth + rightDepth;
result = Math.max(result, zhiJin);
System.out.println(zhiJin + "," + result);
return Math.max(leftDepth, rightDepth) + 1;
}
}
运行结果：
复杂度（DFS复杂度）
- 时间复杂度：O(n)
- 空间复杂度：O(height)，其中 height 表示二叉树的高度
好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！
