leetCode 98.Validate Binary Search Tree (有效二叉搜索树) 答题思路和方法

leetCode 98.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.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

思路：判断是否二叉搜索树，按照定义判断即可，比较简单。

代码如下：

/**
 * 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){
            return true;
        }
        //判断左子树的值是否全比根小,右子树是否全比根大，不是则返回false
        if(!isLessThan(root, root.left) || !isGreaterThan(root, root.right)){
        	return false;
        }

        //如果左右子树均为空，为真
        boolean temp = true;
        //判断左子树
        if(root.left != null){
        	if(root.val > root.left.val){
        		temp = isValidBST(root.left);
        	}else{
        		temp = false;
        	}
        }
        //如果左子树成立，判断右右子树
        if(temp && root.right != null){
        	if(root.right.val > root.val){
        		temp = isValidBST(root.right);
        	}else{
        		temp = false;
        	}
        }
        return temp;
    }
    /**
     * 判断左子树是否全比根节点小
     * @param root
     * @param left
     * @return
     */
    private boolean isLessThan(TreeNode root, TreeNode left){
    	if(left == null){
    		return true;
    	}
    	boolean temp = false;
    	if(left.val < root.val){
    		temp = isLessThan(root, left.left) && isLessThan(root, left.right);
    	}
    	return temp;
    }
	
    /**
     * 判断右子树全比根节点大
     * @param root
     * @param right
     * @return
     */
    private boolean isGreaterThan(TreeNode root, TreeNode right){
    	if(right == null){
    		return true;
    	}
    	boolean temp = false;
    	if(right.val > root.val){
    		temp = isGreaterThan(root, right.left) && isGreaterThan(root, right.right);
    	}
    	return temp;
    }
}

另一种比较简洁的代码方式：

/**
 * 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){
            return true;
        }
        //用long是因为要考虑Integer.MIn和Max的冲突
        return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    /**
     * 判断根节点的是否在左右届中间
     * 是则继续递归判断左右，不是则返回false
     */
    private boolean check(TreeNode root, long l, long r){
    	if(root == null)
    		return true;
    	return root.val > l && root.val < r && 
    			check(root.left,l,root.val) && check(root.right, root.val, r);
    }
}