Description
Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.
Example
Input: [10,5,15,1,8,null,7], Output: 3
Idea
Recursively compute the number of nodes, whether the current tree is a BST, the size of the largest BST subtree in the current tree, min value, and max value.
Solution
class Solution {
private:
// info[0] stores size of largest BST subtree
// info[1] stores whether the tree is BST
// info[2] stores size of current tree
// info[3] stores min
// info[4] stores max
void largestBSTSubtreeHelper(TreeNode *root, vector<int> &info) {
if (!root) {
info.push_back(0);
info.push_back(1);
info.push_back(0);
info.push_back(INT_MAX);
info.push_back(INT_MIN);
} else {
vector<int> leftInfo, rightInfo;
largestBSTSubtreeHelper(root->left, leftInfo);
largestBSTSubtreeHelper(root->right, rightInfo);
int currSize = 1 + leftInfo[2] + rightInfo[2];
int currMin = min(root->val, min(leftInfo[3], rightInfo[3]));
int currMax = max(root->val, max(leftInfo[4], rightInfo[4]));
bool isBST = leftInfo[1] > 0 && rightInfo[1] > 0;
if (root->val <= leftInfo[4] || root->val >= rightInfo[3]) isBST = false;
int largestBST = isBST ? currSize : max(leftInfo[0], rightInfo[0]);
info.push_back(largestBST);
info.push_back(isBST ? 1 : 0);
info.push_back(currSize);
info.push_back(currMin);
info.push_back(currMax);
}
}
public:
int largestBSTSubtree(TreeNode* root) {
vector<int> info;
largestBSTSubtreeHelper(root, info);
return info[0];
}
};
73 / 73 test cases passed.
Runtime: 12 ms
