LeetCode 1373 Maximum Sum BST in Binary Tree
概述
https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/
这是一道 hard 题。
递归法
这里比较麻烦的一点是，判断子树是否为合法的 BST 时，我们还得区分全局范围和本地范围。
好麻烦，hard 果然是 hard，哭了。
看了一下 labuladong 的教程：
站在当前节点的视角，需要知道以下具体信息：
- 左右子树是否是 BST。
- 左子树的最大值和右子树的最小值。
- 左右子树的节点值之和。
有一点要注意啊，因为值可能为负数，所以我们必须存一个全局变量来记录最大值，否则传到根节点后其可能反而会变小。
另外这道题有问题，其将 nullptr 也视为 BST。
class Solution {
public:
int ans = INT_MIN;
int maxSumBST(TreeNode* root) {
helper(root);
if (ans < 0) return 0; // this question is weird
return ans;
}
vector<int> helper(TreeNode* root) {
vector<int> res(4, 0); // isBST, maxSumBST, maxValue, minValue
if (!root) {
res[0] = 1;
res[1] = INT_MIN;
res[2] = INT_MIN;
res[3] = INT_MAX;
return res;
}
auto lres = helper(root->left);
auto rres = helper(root->right);
bool isBST = lres[0] == 1 && rres[0] == 1 && root->val > lres[2] && root->val < rres[3];
if (isBST) {
res[0] = 1;
res[1] = root->val;
if (root->left) res[1] += lres[1];
if (root->right) res[1] += rres[1];
ans = max(ans, res[1]);
} else {
res[0] = 0;
res[1] = max(lres[1], rres[1]);
}
res[2] = max(root->val, max(lres[2], rres[2]));
res[3] = min(root->val, min(lres[3], rres[3]));
return res;
}
};