题目描述：
给出一棵以 $root$ 为根的二叉树，找出其中最大的二叉搜索树的最大键值和。
数据范围：
$1\le n \le 4\times 10^4$
题解：
二叉搜索树，左子树小于该节点，右子树大于该节点。
使用如下结构记录
1
2
3
4
5
6
7
| struct NodeStatus
{
bool isBst;
int maxx;
int minx;
int sum;
};
|
然后直接后续遍历，如果两个子树都是bst，那么就判断 left.maxx < root->val && root->val < right.minx，如果为真，则该子树是bst，更新信息， $maxx = \max(val, right.max), minx = \min(val, left.min)$
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const int INF = 0x3f3f3f3f;
struct NodeStatus
{
bool isBst;
int maxx;
int minx;
int sum;
};
int ans = 0;
NodeStatus dfs(TreeNode *root)
{
if (root == nullptr)
return {true, -INF, INF, 0};
NodeStatus left = dfs(root->left);
NodeStatus right = dfs(root->right);
if (left.isBst && right.isBst && left.maxx < root->val && root->val < right.minx)
{
int val = left.sum + root->val + right.sum;
ans = max(ans, val);
return {true, max(root->val, right.maxx), min(root->val, left.minx), val};
}
else
return {false, 0, 0, 0};
}
int maxSumBST(TreeNode *root)
{
dfs(root);
return ans;
}
};
|