题解 | #农场最大产奶牛群# 树形DP

农场最大产奶牛群

https://www.nowcoder.com/practice/16d827f124e14e05b988f3002e7cd651

知识点

树形DP DFS

思路

答案一定是从某一个节点,到两个叶子结点的路径和。我们可以用树形DP进行解决。

dfs返回从某一节点作为根节点的子树到达叶子结点的最大路径和,用经左子树和右子树的两个路径和 + 该结点的val来更新答案,然后将该结点的val加入路径后计算最大到叶子结点路径和,返回父节点。

时间复杂度

每个节点只遍历一次,O(n)

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 res = 0;
    int maxMilkSum(TreeNode* root) {
        if (!root) return 0;
        dfs(root);
        return res;
    }
    // 返回以root为根节点的子树中的最大的到叶子节点路径和
    int dfs(TreeNode* root) {
        if (!root) return 0;
        auto l = dfs(root->left), r = dfs(root->right);
        res = max(res, l + r + root->val);
        return max(l, r) + root->val;
    }
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-23 13:41
求求各位大佬
gtgt..:硕士怎么会把简历写成这样
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务