验证二叉搜索树

题目

思路

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

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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);
    }
}