验证二叉搜索树

题目

思路

• root starts with (-inf, +inf)
• left child inherits (min, root.val)
• right child inherits (root.val, max)

Java

class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean dfs(TreeNode node, long low, long high) {
        if (node == null) {
            return true;
        }

        long v = node.val;
        if (v <= low || v >= high) {
            return false;
        }
        return dfs(node.left, low, v) && dfs(node.right, v, high);
    }
}