题解 | #农场最大产奶牛群# 树形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-17 12:14
门头沟学院 Java
点赞 评论 收藏
分享
07-18 18:45
已编辑
中山职业技术学院 Java
投递TP-LINK等公司7个岗位
点赞 评论 收藏
分享
Lorn的意义:1.你这根本就不会写简历呀,了解太少了 2.你这些项目经历感觉真的没啥亮点啊,描述的不行,重写书写一下让人看到核心,就继续海投 注意七八月份ofer还是比较多的,越往后机会越少,抓住时机,抓紧检查疏漏,加油查看图片
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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