K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
合法二叉搜索树的定义为:左子树中所有节点的值均小于当前节点的值,右子树中所有节点的值均大于当前节点的值,且左右子树也分别是合法二叉搜索树。
仅需递归验证每个节点的左孩子值小于当前节点、右孩子值大于当前节点,即可完成校验
递归校验时需为每个节点传递允许的取值范围(下界low、上界high),当前节点值必须在(low, high)区间内;递归校验左子树时将上界更新为当前节点值,校验右子树时将下界更新为当前节点值
递归验证二叉搜索树的时间复杂度为O(h),其中h为树的高度
递归方法无法处理节点值为整数边界(如编程语言定义的最小整数值、最大整数值)的场景