8 ms Recursive Solution in C++


  • 0
    H
    class Solution {
    public:
    	int maxNodes;
    	int isBST(TreeNode* root, pair<TreeNode*, TreeNode*>& nodes){
    		if (!root) return 0;
    		int leftnodes = 0, rightnodes = 0, retnodes;
    		pair<TreeNode*, TreeNode*> left, right;
    		leftnodes = isBST(root->left, left);
    		rightnodes = isBST(root->right,right);
    		if (leftnodes == -1 || rightnodes == -1) return -1;
    		if (leftnodes == 0) {
    			left.first = root; 
    			left.second = root;
    		}
    		if (rightnodes == 0) {
    			right.first = root;
    			right.second = root;
    		}
    		if (root->val >= left.second->val && root->val <= right.first->val){
    			retnodes = leftnodes + rightnodes + 1;
    			maxNodes = maxNodes > retnodes ? maxNodes : retnodes;
    			nodes.first = left.first;
    			nodes.second = right.second;
    			return retnodes;
    		}
    		else return -1;
    	}
        int largestBSTSubtree(TreeNode* root) {
            maxNodes = 0;
    		pair<TreeNode*, TreeNode*> res;
    		isBST(root, res);
    		return maxNodes;
        }
    };

Log in to reply
 

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