C++ 9ms O(n) solution


  • 0
    S

    Basic thought is to use recursion to find if a subtree is a valid binary search tree, if it is, count the number of nodes by adding left subtree and right subtree and root itself; otherwise, return bigger result of left subtree and right subtree. And in the same recursion route, find the minimum value and maximum value of the subtree which need to be used in the validation:

    class Solution {
    public:
        int largestBSTSubtree(TreeNode* root) {
            bool endsAtHere;
            int minVal, maxVal;
            return recur(root, endsAtHere, minVal, maxVal);
        }
        
        int recur(TreeNode* node, bool& endsAtHere, int& minVal, int& maxVal) {
            if(node==NULL){
                endsAtHere = true;
                minVal = INT_MAX;
                maxVal = INT_MIN;
                return 0;
            }
            int leftMin, rightMin, leftMax, rightMax;
            bool endsAtRightRoot = false;
            bool endsAtLeftRoot = false;
            int leftRes = recur(node->left, endsAtLeftRoot, leftMin, leftMax);
            int rightRes = recur(node->right, endsAtRightRoot, rightMin, rightMax);
            minVal = min(min(node->val, leftMin), rightMin);
            maxVal = max(max(node->val, leftMax), rightMax);
            if(endsAtLeftRoot && endsAtRightRoot && node->val > leftMax && node->val < rightMin){
                endsAtHere = true;
                return leftRes + rightRes + 1;
            }
            endsAtHere = false;
            return max(leftRes, rightRes);
        }
    };
    
    

Log in to reply
 

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