Description

给定\(n\)个结点的二叉树,每个结点具有权值\(v_i\),求出树上的最大和路径(可以不经过根结点)。

Constraints

  • \(1 \le n \le 3 \cdot 10^4\)
  • \(-1000 \le v_i \le 1000\)

Solution

设\(dp[u]\)为以结点\(u\)为根的子树的最长路径(并且以\(u\)为起点)。

求出后组合一下\(u\)的左子树和右子树情况即可。

注意存在负数,因此左右子树可以不选择。

687也是差不多的题目。

Code

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        unordered_map<TreeNode*, int> dp;

        auto DP = [&](auto &&DP, TreeNode *cur) {
            if(!cur) return 0;
            auto lc = cur->left;
            auto rc = cur->right;
            auto mx = max({DP(DP, lc), DP(DP, rc), 0});
            return dp[cur] = mx + cur->val;
        };

        int ans = DP(DP, root);
        for(auto [cur, _] : dp) {
            auto lc = cur->left;
            auto rc = cur->right;
            auto v = cur->val;
            auto lans = lc ? dp[lc] : 0;
            auto rans = rc ? dp[rc] : 0;
            ans = max({
                ans,
                v,
                lans + v,
                rans + v,
                lans + v + rans
            });
        }
        return ans;
    }
};

LeetCode-124 Binary Tree Maximum Path Sum