题目地址：https://leetcode-cn.com/problems/largest-bst-subtree/
题目描述
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.
Note:
- A subtree must include all of its descendants.
Example:
Input: [10,5,15,1,8,null,7]
10
/ \
5 15
/ \ \
1 8 7
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree's size, which is 3.
Follow up:
- Can you figure out ways to solve it with O(n) time complexity?
题目大意
找出一个树中最大的BST有多少个节点。
解题方法
DFS
如果用简单的方法做，就是先判断每个树是不是BST，如果是则返回其节点个数，如果不是就递归他的左右子树，最后结果要用最大值。
C++代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int largestBSTSubtree(TreeNode* root) {
if (!root) return 0;
int res = 0;
if (isBST(root, INT_MIN, INT_MAX)) {
return countNodes(root);
}
res = max(res, largestBSTSubtree(root->left));
res = max(res, largestBSTSubtree(root->right));
return res;
}
bool isBST(TreeNode* root, int minVal, int maxVal) {
if (!root) return true;
if (root->val >= maxVal)
return false;
if (root->val <= minVal)
return false;
return isBST(root->left, minVal, root->val) && isBST(root->right, root->val, maxVal);
}
int countNodes(TreeNode* root) {
if (!root) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
private:
int res = 0;
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发