O(n) solution with muti-things return in C++


  • 1
    Z
    class Solution {
    public:
        struct NodeInfo{
            bool valid = false;
            int mostLeft = INT_MIN;
            int mostRight = INT_MAX;
            int count = 0;
        };
        int largestBSTSubtree(TreeNode* root) {
            NodeInfo info = helper(root);
            return info.count;
        }
        NodeInfo helper(TreeNode *root){
            if(!root){
                NodeInfo info;
                info.valid = true;
                info.mostRight = INT_MIN;
                info.mostLeft = INT_MAX;
                info.count = 0;
                return info;
            }
            NodeInfo left = helper(root->left);
            NodeInfo right = helper(root->right);
            NodeInfo info;
            info.valid = left.valid && right.valid && left.mostRight<root->val && right.mostLeft>root->val;
            if(info.valid){
                info.mostLeft = min(left.mostLeft,root->val);
                info.mostRight = max(root->val,right.mostRight);
                info.count = left.count+right.count+1;
            }
            else{
                info.count = max(left.count,right.count);
            }
            return info;
        }
    };

Log in to reply
 

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