leetcode: Validate Binary Search Tree

问题描述：

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

 

Example 1:

    2
   / \
  1   3

Binary tree [2,1,3], return true.

 

Example 2:

    1
   / \
  2   3

Binary tree [1,2,3], return false.

 

 

 

原问题链接：https://leetcode.com/problems/validate-binary-search-tree/

 

问题分析

最初想法

　　这个问题粗看的时候很简单，我们有一种递归的思路。就是对于里面每个节点，判断它如果有左右子节点的话，它的当前节点应该大于它的左子节点的值，如果有右子节点的话，应该小于它的右子节点的值。于是得到如下的实现代码：

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return true;
        if(root.left != null && root.left.val >= root.val) return false;
        if(root.right != null && root.right.val <= root.val) return false;
        return isValidBST(root.left) && isValidBST(root.right);
    }
}

　　可是在实际执行的过程中却报错了，对于如下的输入来说：

[10,5,15,null,null,6,20]

　　它相当于是一棵如下的树：

 

　　在上图，我们虽然每个点都满足了它的左子节点比当前节点小，右子节点值比当前节点大，但是出现了一个节点15的左子节点小于根节点15的情况。这和前面二叉搜索树的定义有冲突。这是因为我们前面忽略了一个问题，在二叉搜索树里，一个节点比它的左子树的所有元素要大，比它右子树的所有元素要小。而这里仅仅根据一个节点和它的左右子节点的比较关系是不够的。

 

修改

　　于是，我们需要根据前面的情况进行修改。 在任何一个节点，我们需要定义这个节点所在的范围。因此需要引入两个变量，min, max。分别表示它所在的最大值和最小值。这样，对于任何一个节点来说，它的左子节点对应的值的范围是[min, node.val]，就是从min到当前节点的值。而右子节点值对应的范围则是[node.val, max]。

　　于是我们就得到如下的代码：

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private boolean isValidBST(TreeNode node, int min, int max) {
        if(node == null) return true;
        return node.val > min && node.val < max && isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }
}

　　可是我们运行的时候会发现居然出错了，导致错误结果的是如下的一组输入：

[2147483647]

　　这里的问题就在于，我们当前在递归里设定的初始值为Integer.MAX_VALUE, Integer.MIN_VALUE。它们相当于是两个边界值，而在问题里要求是一个节点的值和它的左右子节点不能是相等的关系。所以会出现还差一点的情况。 

　　这里的问题就是在于我们初始设定了这么两个极端的值，但是如果正好某个节点的值就是这两个值的话，我们程序就会出问题。所以在代码里就不应该设定初始的最大和最小值。而且从最初的代码调用里，第一个检查的元素就是根节点，它取任意值都是合理的。所以我们只需要设定在后面的递归里逐步将当前的值作为最大或者最小值传递到后面的调用中来判断就好了。

　　详细的代码实现如下：

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
       return isValidBST(root,null,null);
    
    }
    private boolean isValidBST(TreeNode root, Integer max, Integer min){
        if(root==null)   return true;
        if(max !=null && root.val >= max) return false;
        if(min != null && root.val <= min) return false;
        return isValidBST(root.left, root.val, min) && isValidBST(root.right, max, root.val); 
    }
}

　　上面代码里不是利用原生的int类型，而是改为使用Integer类型的参数。这样在最开始的情况下，将最大值和最小值都设置为null，可以规避硬设定一个初始值的问题。