题解 | #牛群的最长距离# 树的直径 树形DP

知识点

树的直径 树形DP

思路

树的直径板子题，有两次DFS的解法和树形DP的解法，这里是树形DP的做法。

我们需要用DFS得到每个节点到叶子节点的最长距离，在每个节点处用左子树的最长距离和右子树最长距离以及本节点更新答案。

由于我们求的是节点数，边数应该是-1。

时间复杂度

每个节点遍历常数次

AC code（C++）

/**
 * 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 diameterOfBinaryTree(TreeNode* root) {
        if (!root) return 0; 
        int res = 0;
        function<int(TreeNode*)> dfs = [&](TreeNode* root) {
            if (!root) return 0;
            auto l = dfs(root->left);
            auto r = dfs(root->right);
            res = max(res, l + r + 1);
            return max(l, r) + 1;
        };
        dfs(root);
        return res - 1;
    }
};