10 lines c++ with comments


  • 0
    // Use a size 3 vector, contains {subtree_size, lower_bound, upper_bound}.
    
    class Solution {
    public:
        int largestBSTSubtree(TreeNode* root) {
            if(!root) return 0;
    	traverse(root);
    	return result;
        }
    private:
        int result = 0;
        vector<int> traverse(TreeNode* root){
    	if(!root) return vector<int>{0, INT_MAX, INT_MIN}; //{subtree_size, lower_bound, upper_bound}.
    	vector<int> l = traverse(root->left);
    	vector<int> r = traverse(root->right);
    	if(l[0] == -1 || r[0] == -1 || l[2] >= root->val || r[1] <= root->val) return vector<int>{-1, 0, 0};
    	result = max(result, l[0] + r[0] + 1);
    	return vector<int>{l[0] + r[0] + 1, min(l[1], root->val), max(r[2], root->val)};
        }
    };
    

    Thanks to @mach7's post


Log in to reply
 

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