二叉树权值

题目描述

给定一棵二叉树的根节点 root，定义如下递归过程 dfs(node)，并用 ans 统计递归调用中访问到的非空节点数量：

1. 若当前节点为空，则直接返回。
2. 对当前非空节点执行 ans++。
3. 若当前节点为叶子节点，则直接返回。
4. 若以当前节点为根的整棵子树是一棵二叉搜索树（BST），则直接返回。
5. 否则继续递归调用 dfs(node.left) 和 dfs(node.right)。

调用完 dfs(root) 后，最终得到的 ans 称为这棵树的权值。

对于一棵二叉搜索树（BST），要求其每个节点都满足：

• 左子树所有节点值都严格小于当前节点值；
• 右子树所有节点值都严格大于当前节点值；
• 左右子树本身也都是二叉搜索树。

请你计算并输出给定二叉树的权值。

输入格式

第一行输入一个整数 n，表示二叉树层序序列的长度。

第二行输入 n 个字符串，表示二叉树的层序遍历结果，其中：

• 非 null 字符串表示该节点的整数值；
• null 表示该位置为空节点。

保证输入序列能够唯一确定一棵二叉树，且根节点非空。

输出格式

输出一个整数，表示这棵二叉树的权值。

数据范围

1 <= n <= 2 * 10^5

节点值的范围为 [-10^9, 10^9]。

样例 1

输入

7
10 5 15 null null 6 20

输出

3

说明

整棵树不是 BST，因此会访问根节点 10，然后继续访问左右子树。左子树 5 是叶子节点，右子树 15-6-20 不是 BST，因此最终访问到的非空节点数为 3。