验证二叉搜索树

已关闭

dadingPython / C++入场费 2 金币1 次提交

题目描述

给定一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树（BST）。有效的 BST 定义为：节点的左子树只包含小于当前节点的数；节点的右子树只包含大于当前节点的数；所有左子树和右子树自身必须也是二叉搜索树。输入以层序遍历的方式给出，空节点用 null 表示。

第一行一个整数 n，表示层序遍历序列的长度。第二行 n 个值，表示二叉树的层序遍历（空节点用 null 表示，整数范围 -2^31 到 2^31-1）。

输出 true 或 false，表示该树是否为有效的二叉搜索树。

样例 1

输入：

7
2 1 3 null null null null

输出：

true

样例 2

输入：

7
5 1 4 null null 3 6

输出：

false

中序遍历 BST 得到的序列应当是严格递增的。注意边界条件：节点值可能等于 INT_MIN/INT_MAX，不能简单用开区间判断。