# 333. Largest BST Subtree 最大 BST 子树

@TOC

## # 题目描述

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.
``````

• Can you figure out ways to solve it with O(n) time complexity?

## # 解题方法

### # DFS

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;
};
``````

## # 日期

2019 年 9 月 20 日 —— 是选择中国互联网式加班？还是外企式养生？