二叉树节点之和的问题

Question

二叉树节点之和（保证修剪完之后节点值之和最大）的问题，请教 请教。

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

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);
    }
};

Answer 1

该回答引用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;
}