give nu 2023-02-26 10:55 采纳率: 66.7%
浏览 30
已结题

二叉树节点之和的问题

二叉树节点之和(保证修剪完之后节点值之和最大)的问题,请教 请教。

img


目前只会写计算从根节点到叶子节点的代码。请教一下这个题目,看了一天了还不会写。

class Solution {
public:
    int dfs(TreeNode* root, int prevSum) {
        if (root == nullptr) {
            return 0;
        }
        int sum = prevSum * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr) {
            return sum;
        } else {
            return dfs(root->left, sum) + dfs(root->right, sum);
        }
    }
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
};



  • 写回答

2条回答 默认 最新

  • BitGPT 2023-02-26 10:59
    关注

    该回答引用ChatGPT

    以下是一种使用动态规划(DP)的解决方案。

    定义dp[i][0]表示以结点i为根的子树中,不剪掉结点i时的最大美丽值,dp[i][1]表示以结点i为根的子树中,剪掉结点i时的最大美丽值。

    对于dp[i][0],可以使用以下递归公式:

    dp[i][0] = beauty[i] + max(dp[lson][0], 0) + max(dp[rson][0], 0)

    其中beauty[i]表示结点i的美丽值,lson和rson分别表示结点i的左右儿子。如果子树的美丽值小于0,可以不选,所以使用max(dp[lson][0], 0)和max(dp[rson][0], 0)。

    对于dp[i][1],可以使用以下递归公式:

    dp[i][1] = max(dp[lson][0], 0) + max(dp[rson][0], 0)

    因为剪掉结点i时,其左右子树的根节点都会被剪掉,所以子树的美丽值只能由dp[lson][0]和dp[rson][0]中的最大值组成。

    最终答案为max(dp[1][0], dp[1][1]),其中1表示整棵树的根节点。

    以下是C++代码实现:

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int N = 10010;
    int n;
    int beauty[N];
    int lson[N], rson[N];
    int dp[N][2];
    
    void dfs(int u) {
        if (lson[u]) {
            dfs(lson[u]);
            dp[u][0] += max(dp[lson[u]][0], 0);
            dp[u][1] += max(dp[lson[u]][0], 0);
        }
        if (rson[u]) {
            dfs(rson[u]);
            dp[u][0] += max(dp[rson[u]][0], 0);
            dp[u][1] += max(dp[rson[u]][0], 0);
        }
    }
    
    int main() {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> beauty[i];
        for (int i = 1; i <= n; i++) {
            int u;
            cin >> u >> lson[u] >> rson[u];
        }
        dfs(1);
        int ans = max(dp[1][0], dp[1][1]);
        cout << ans << endl;
        return 0;
    }
    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 3月6日
  • 已采纳回答 2月26日
  • 创建了问题 2月26日

悬赏问题

  • ¥20 Yolov5训练报错
  • ¥15 Unity发布gzip压缩的webgl之后让浏览器可以正常显示画面
  • ¥15 有没有人知道这种提示怎么关?现在不做ts项目了不知道咋关了,求解,现在我以前的js项目都是这种提示了
  • ¥15 为什么mysql做了碎片化处理data_free还是很高
  • ¥15 single positional indexer is out-of-bounds
  • ¥15 LSTM 模型数据量需要多少?
  • ¥15 mysql数据抓包开发报表
  • ¥15 linux系统下安装office打不开
  • ¥20 rsync脚本分发错误,文件不齐全
  • ¥15 labview顺序结构与时间延时