题目

类型：Tree

难度：中等

验证二叉搜索树 - 图1

解题思路

1、如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。

2、设计一个递归函数 helper(root, lower, upper)来递归判断，以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r)的范围内（注意是开区间）。如果 root节点的值 val 不在(l,r)的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。

3、在递归调用左子树时，需要把上界 upper 改为 root.val，即调用 helper(root.left, lower, root.val)，因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时，需要把下界 lower 改为root.val，即调用 helper(root.right, root.val, upper)。

4、函数递归调用的入口为 helper(root, -inf, +inf)， inf 表示一个无穷大的值。

代码

  1. class Solution {
  2.     public boolean isValidBST(TreeNode root) {
  3.         return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
  4.     }
  6.     public boolean isValidBST(TreeNode node, long lower, long upper) {
  7.         if (node == null) {
  8.             return true;
  9.         }
  10.         if (node.val <= lower || node.val >= upper) {
  11.             return false;
  12.         }
  13.         return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
  14.     }
  15. }