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

知识点：

二叉树/图的直径/DFS/BFS

分析：

这道题，可以看作是求二叉树的直径。当然，也可以求图的直径，二叉树就是边权为1的有向图。

求直径的时候，思路也很简单。

对于每一个点，求这个点x的最远的点u，再求距离u最远的点。这条路径就是最长的路径。

可以用DFS或者BFS来求/// BFS不易爆栈，推荐用BFS，答案实例使用DFS。

编程语言：

完整代码：

class Solution {
  public:
    int ans = 0;
    int dfs(TreeNode* u, TreeNode* father) {
        int dist = 0;
        int d1 = 0, d2 = 0;
        if (u->left) {
            int j = u->left->val;
            int d = dfs(u->left, u) + 1;
            dist = max(d, dist);
            if (d > d1) d2 = d1, d1 = d;
            else if (d > d2) d2 = d;
        }
        if (u->right) {
            int j = u->right->val;
            int d = dfs(u->right, u) + 1;
            dist = max(d, dist);
            if (d > d1) d2 = d1, d1 = d;
            else if (d > d2) d2 = d;
        }

        ans = max(ans, d1 + d2);
        return dist;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        if(root == nullptr) return 0;
        if(!root->left && !root->right) return 0;
        dfs(root, nullptr);
        return ans;
    }
};