Share my C++ solution with only one dfs-pass


  • 0
    O
    /**
     * 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) {
            map<TreeNode*, int> sz;
            map<TreeNode*, pair<int, int> > min_max;
            int ans = 0;
            check(root, sz, min_max, ans);
            return ans;
        }
        #define mi first
        #define ma second
        #define MP make_pair
        bool check(TreeNode *root, map<TreeNode*, int> &sz, map<TreeNode*, pair<int, int> > &min_max, int &ans) {
            if (root == NULL) return true;
            bool left_good = check(root->left, sz, min_max, ans),
                right_good = check(root->right, sz, min_max, ans);
            if (!left_good or !right_good) return false;
            if (root->left != NULL and min_max[root->left].ma > root->val) return false;
            if (root->right != NULL and min_max[root->right].mi < root->val) return false;
            min_max[root] = MP(root->val, root->val);
            if (root->left != NULL) min_max[root].mi = min_max[root->left].mi;
            if (root->right != NULL) min_max[root].ma = min_max[root->right].ma;
            sz[root] = 1;
            if (root->left != NULL) sz[root] += sz[root->left];
            if (root->right != NULL) sz[root] += sz[root->right];
            ans = max(ans, sz[root]);
            return true;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.