题目
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ 2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
方法
递归法
在计算深度时计算的是节点的个数，题目所求为边的个数，因此要res-1
- 时间复杂度：O(n)，n为二叉树的节点数
- 空间复杂度：O(h)，h为二叉树的深度，每次递归都要分配栈空间，递归的次数取决于二叉树的深度
class Solution {
int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
findMaxDepth(root);
return res-1;
}
private int findMaxDepth(TreeNode root){
if(root==null){
return 0;
}
int left = findMaxDepth(root.left);
int right = findMaxDepth(root.right);
res = Math.max(res,left+right+1);
return Math.max(left,right)+1;
}
}