二叉树

验证二叉搜索树

中等#98Java时间 O(n)空间 O(h)

题目要做什么

判断是否为严格二叉搜索树:每个节点的整个左子树都小于它,整个右子树都大于它。相等也不合法。

题目示例输入root = [5,1,4,null,null,3,6]
题目示例输出false

01 为什么这样做

递归传入允许值的开区间。进入左边缩小上界,进入右边提高下界;祖先的限制会一路传下去。用 long 边界避免 int 极值冲突。

始终成立的条件

节点必须严格位于所有祖先共同确定的 (low, high) 内。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public boolean isValidBST(TreeNode root) {3        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);4    }5    private boolean valid(TreeNode node, long low, long high) {6        if (node == null) return true;7        if (node.val <= low || node.val >= high) return false;8        boolean left = valid(node.left, low, node.val);9        return left && valid(node.right, node.val, high);10    }11}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索