最大 BST 子树

发表于

给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，其中最大指的是子树节点数最多的。
输入: [10,5,15,1,8,null,7]

10
/ \
5 15
/ \ \
1 8 7
其中最大的BTS子树是 5 1 8

1.判断是不是BTS：

1
2
3
4
5
6
7
8
9
10
bool bst(TreeNode* root) {
        return pd(root, INT_MIN, INT_MAX);
}
bool pd(TreeNode*root, int low, int high) {
        if (root == NULL) return 1;
        if (root->val > low && root->val <high) {
            return pd (root->left, low, root->val) && pd(root->right, root->val, high);
        }
        return 0;
}

2.统计某个树的结点数量：

1
2
3
4
5
6
int num(TreeNode* root) {
        if (root == NULL) return 0;
        int left = num(root->left);
        int right = num(root->right);
        return left + right + 1;
}

3.实现：

1
2
3
4
5
6
7
8
9
10
11
12
int largestBSTSubtree(TreeNode* root) {
      if (root == NULL) {
          return 0;
      }
      if (bst(root)) {
          return  num(root);
      }
      int left = largestBSTSubtree(root->left);
      int right = largestBSTSubtree(root->right);
      
      return max(left, right);
  }