题目描述

解题思路

本题求的直径也就是两个节点之间的最大值，注意可以经过根节点，也可以不经过根节点，例如：

此时最大直径便不经过根节点。所以我们可以求每个节点的深度，再将左右两边深度相加减一就可以该节点的得到直径，但是由于直径不只经过根节点，所以需要使用一个变量ans来记录每个节点左右子树的最大深度，遇到最大则更新ans，最后返回ans-1，就是最长的直径。

注意返回值一定需要经过根节点，所以需要求出左右子树的最大直径加上根节点。而求每个节点的最大直径可以经过根节点，也可以不经过。

class Solution {
    int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        getDepth(root);
        return ans - 1;
    }
    public int getDepth(TreeNode root) {
        if (root == null) return 0;
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        ans = Math.max(ans, 1 + left + right);
        return 1 + Math.max(left, right);
    }
}