tree

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