题解 | #牛群的最长距离#

第一次遇到想了好几分钟，解法好巧妙：

1. 我们假设每个顶点为中转站 (顶点左边的点经过他 到右边的点 或者到顶点本身)。
2. 那其实就是算出以这个顶点为根结点的树的左右子树最大深度和。
3. 可以利用DFS计算深度，并每次取MAX更新结果

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    int ans = 0;
    int getHeight(TreeNode* root) {
        if (!root) return 0;
        int n = getHeight(root->left);
        int m = getHeight(root->right);
        ans = max(ans, n + m);
        return max(n, m) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        getHeight(root);
        return ans;
    }
};