c++ clean O(n) time recursive solution


  • 0

    Only used 3 reference variables, less space complexity. The function int bstSize(...) returns -1 if the current subtree with root node is not a valid BST, else it returns the size of this subtree.

    int largestBSTSubtree(TreeNode* root) {
        int result = 0, low = 0, high = 0;
        if (!root) return result;
        bstSize(root, low, high, result);
        return result;
    }
    
    int bstSize(TreeNode* node, int& low, int& high, int& result) {
        if (!node) return 0;
        bool valid = true;
        int left = bstSize(node->left, low, high, result);
        int low_bound = left == 0 ? node->val : low;
        if (left == -1 || (left > 0 && node->val <= high)) valid = false;
        int right = bstSize(node->right, low, high, result);
        int up_bound = right == 0 ? node->val : high;
        if (right == -1 || (right > 0 && node->val >= low)) valid = false;
        low = low_bound;
        high = up_bound;
        int total = valid ? left + right + 1 : -1;
        result = max(result, total);
        return total;
    }
    

Log in to reply
 

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