最大BST子树

题目描述

给定一棵普通二叉树（不保证为二叉搜索树），求出树中节点数量最多的合法二叉搜索子树的节点个数。

二叉搜索树 BST 定义： 任意节点满足：左子树所有节点值严格小于当前节点值，右子树所有节点值严格大于当前节点值，且左右子树均为 BST。

子树定义：以某个节点为根，包含其全部后代。单个节点一定是合法 BST。

输入格式

一行若干整数，为二叉树的层序遍历序列，-1 表示空节点。

输出格式

输出一个整数，表示最大 BST 子树的节点数。

样例输入 1

10 5 15 1 8 -1 7 -1 -1 -1 -1 -1 -1

样例输出 1

3

样例输入 2

3 2 4 -1 -1 1 -1

样例输出 2

2

数据范围

• 节点总数不超过 $10^4$
• 节点权值范围 $[-10^5,10^5]$