lc333
DFS遍历树，每个节点记录子树最值和BST节点数（-1非BST）
验证当前节点为根的子树是否BST，实时更最大BST节点数
class Solution {
int ans = 0;
using T = tuple<int, int, int>;
public:
int largestBSTSubtree(TreeNode* root) {
if (!root) return 0;
dfs(root);
return ans;
}
T dfs(TreeNode* n)
{
int mn = n->val, mx = n->val;
int ls = 0, rs = 0;
bool ok = true;
if (n->left) {
auto [lm, lx, lz] = dfs(n->left);
if (lz == -1 || n->val <= lx) ok = false;
mn = min(mn, lm);
mx = max(mx, lx);
ls = lz;
}
if (n->right) {
auto [rm, rx, rz] = dfs(n->right);
if (rz == -1 || n->val >= rm) ok = false;
mn = min(mn, rm);
mx = max(mx, rx);
rs = rz;
}
int sz = ok ? (1 + ls + rs) : -1;
if (sz != -1) ans = max(ans, sz);
return {mn, mx, sz};
}
};
