树的直径
1.求树的最大路径,每条直径一定会有一个高点,直径就是高点的左边+高点的右边即可,通过递归遍历每个点,从而求出每个点的直径
2.求左右路径的最大长度的时,需要加上来源点的那条边,所以返回值是:Math.max(left, right) + 1
具体如图所示
class Solution {
public int max = 0;
public int dfs(TreeNode root) {
if(root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
max = Math.max(max, left + right);
return Math.max(left, right) + 1;
}
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return max;
}
}