/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// 计算树的直径的长度
// 树的直径的定义是树上两个结点之间最长路径的长度
// 该路径可能经过，也可能不经过根结点

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 1;   // 初始化为 1 而不是 0 以应对边界情况
        depth(root, ans);
        return ans - 1;
    }

private:
    // 求以 root 为根结点的子树的深度
    // 在搜索过程中，通过左右两子树的深度相加来更新已知的树的最大直径
    int depth(TreeNode* root, int& ans) {
        if(!root) return 0;
        int left = depth(root->left, ans);
        int right = depth(root->right, ans);
        ans = max(ans, left + right + 1);
        return max(left, right) + 1;
    }
};