333. Largest BST Subtree

O(n) time O(h) space
postorder traversal

/**
 * 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 largestBSTSubtree(TreeNode* root) {
        return get<0>(dfs(root));
    }

    tuple<int, int, int> dfs(TreeNode *p) { // {以root为根的这棵树的最大BST子树的结点数，最小值，最大值}
        if (!p) return {0, INT_MAX, INT_MIN};
        auto [ln, lmn, lmx] = dfs(p->left);
        auto [rn, rmn, rmx] = dfs(p->right);
        if (lmx >= p->val || rmn <= p->val) return {max(ln, rn), INT_MIN, INT_MAX}; // 如果这棵树不是BST，左右子可能有一个是BST，不是的话也会把那棵子树上最大的BST的结点数返回给上一层
        return {ln + 1 + rn, min(lmn, p->val), max(rmx, p->val)}; // 这里最小值和最大值都要把root考虑进去
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        auto ret = dfs(root);
        return ret[2];
    }

    vector<int> dfs(TreeNode *root) {
        if (!root) return {INT_MAX, INT_MIN, 0}; // {最小值，最大值，以root为根的这棵树的最大BST子树的结点数}
        auto l = dfs(root->left);
        auto r = dfs(root->right);
        if (l[1] < root->val && root->val < r[0]) return {min(l[0], root->val), max(root->val, r[1]), l[2] + r[2] + 1}; // 这里最小值和最大值都要把root考虑进去
        return {INT_MIN, INT_MAX, max(l[2], r[2])}; // 如果这棵树不是BST，左右子可能有一个是BST，不是的话也会把那棵子树上最大的BST的结点数返回给上一层
    }
};