给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

**输入：**root = [1,2,3,4,5]
**输出：**3
**解释：**3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

**输入：**root = [1,2]
**输出：**1

提示：

树中节点数目在范围 [1, 10(4)] 内

-100 <= Node.val <= 100

求得直径所经过的路径一定有一个根节点，

所以题目就变成了寻找一个根节点，他的左右子树深度相加最大

需要一个全局变量，在递归求深度的过程中记录最大的左右子树深度和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int ans = 0;
    int diameterOfBinaryTree(TreeNode *root) {
        if (root == nullptr)
            return 0;
        depth(root);
        return ans;
    }
    int depth(TreeNode *root) {
        if (root == nullptr)
            return 0;
        int l = depth(root->left);
        int r = depth(root->right);
        ans = max(l + r, ans);
        return max(l, r) + 1;
    }
};