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