[lintcode]95.验证二叉查找树

描述

给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵BST定义为：
节点的左子树中的值要严格小于该节点的值。
节点的右子树中的值要严格大于该节点的值。
左右子树也必须是二叉查找树。
一个节点的树也是二叉查找树。

代码

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    public boolean isValidBST(TreeNode root) {
        boolean result = false;
        if (root == null) {
            result = true;
        } else if (root.left == null && root.right == null){
            result = true;
        } else if (root.left == null){
            if (root.right.val > root.val){
                if (root.right.left == null || root.right.left.val > root.val){
                    result = true;
                }
            }
            result = result && isValidBST(root.right);
        } else if (root.right == null){
            if (root.left.val < root.val){
                if (root.left.right == null || root.left.right.val < root.val){
                    result = true;
                }
            }
            result = result && isValidBST(root.left);
        } else {
            boolean tmp = false;
            if (root.left.val < root.val && root.right.val > root.val){
                if (root.right.left == null || root.right.left.val > root.val){
                    result = true;
                }
                if (root.left.right == null || root.left.right.val < root.val){
                    tmp = true;
                }
            }
            result = result && tmp && isValidBST(root.left) && isValidBST(root.right);
        }

        return result;
    }
}