Given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST), where the largest means subtree has the largest number of nodes.
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:
- The left subtree values are less than the value of their parent (root) node's value.
- The right subtree values are greater than the value of their parent (root) node's value.
Note: A subtree must include all of its descendants.
Solution
我们第一需要判断当前树是不是 \(BST\), 第二个就是求当前树的节点个数。
- \(BST\): 用 \(dfs\) 来判断是不是 \(BST\), 对于左子树，其 \(Max=root.val\)；而对于右子树，其\(Min=root.val\)
- \(count\): 如果没节点，返回 \(0\); 否则递归的方式为：
所以在主程序中，我们依旧使用递归即可
点击查看代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
bool check(TreeNode* root, int Min, int Max){
if(!root) return true;
if(root->val <=Min || root->val>=Max){
return false;
}
return check(root->left, Min, root->val) && check(root->right, root->val, Max);
}
int cnt(TreeNode* root){
if(!root)return 0;
return 1+cnt(root->left)+cnt(root->right);
}
public:
int largestBSTSubtree(TreeNode* root) {
if(!root) return 0;
if(check(root, INT_MIN, INT_MAX))return cnt(root);
return max(largestBSTSubtree(root->left), largestBSTSubtree(root->right));
}
};