树上dp
朴素版:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<TreeNode*, int> d1, d2;
void dfs(TreeNode* root) {
if (!root) {
return;
}
dfs(root->left);
dfs(root->right);
d1[root] = max(0, max(d1[root->left], d1[root->right])) + root->val;
d2[root] = max(0, min(d1[root->left], d1[root->right])) + root->val;
}
int maxPathSum(TreeNode* root) {
dfs(root);
int res = -1e9;
for (auto& [k, v] : d1) {
if (k) {
res = max(res, v + d2[k] - k->val);
}
}
return res;
}
};
优化版:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int res = -1e9;
int dfs(TreeNode* root) {
if (!root) {
return 0;
}
int l = dfs(root->left);
int r = dfs(root->right);
int mx = max(0, max(l, r)) + root->val;
int mx_2 = max(0, min(l, r)) + root->val;
res = max(res, mx + mx_2 - root->val);
return root->val + max(0, max(l, r));
}
int maxPathSum(TreeNode* root) {
// 返回以root为根节点到叶子结点的最大长度
dfs(root);
return res;
}
};