LeetCode [中等]98. 验证二叉搜索树

本文介绍: 给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

由于数据范围限制了二叉搜索树中的结点值的取值范围，因此上述取值范围可以用闭区间表示。对于二叉搜索树的每一个子树（包括原二叉搜索树本身），如果其结点值的取值范围是 [low e rBound,up perBound]，子树的根结点值为 mid，则该子树的左子树和右子树的结点值取值范围分别是 [low e rBound,m id−1] 和[mid+1,up perBound]。

判断给定的二叉树是否是二叉搜索树，可以通过判断给定的二叉树的每一个子树是否是二叉搜索树，即每一个子树是否都满足结点值在特定取值范围内。从根结点开始遍历二叉树，对于每个结点，判断其子树的结点值是否在特定取值范围内。

上述过程是一个递归的过程。递归的终止条件有两种情况。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
//精度问题，设置为long类型
public class Solution {
    public bool IsValidBST(TreeNode root) {
       return IsValidBST(root, long.MinValue, long.MaxValue);
    }

    public bool IsValidBST(TreeNode node, long lowerBound, long upperBound)
    {
        if(node == null)
        {
            return true;
        }
        if(node.val < lowerBound || node.val &gt; upperBound)
        {
            return false;
        }
        return IsValidBST(node.left, lowerBound,  (long) node.val - 1) &amp;&amp;
               IsValidBST(node.right,  (long) node.val +1, upperBound);
    }
}