描述

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

如果题目像本题一样有特殊要求则 BST 定义按题目要求来，如果题目没有要求则默认定义如下

二叉查找树性质

二叉查找树功能
O(h)的时间查找，删除，和插入
样例

一个例子：

  2
 / \
1   4
   / \
  3   5

上述这棵二叉树序列化为 {2,1,4,#,#,3,5}

PS

本题其实是简化版的二叉查找树的考题，因为题目去掉了等于的情形，如果考虑等于代码要更复杂

代码

 /**
 * 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;
 *     }
 * }
 */

1. 分治

/**
 * 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;
 *     }
 * }
 */
class ResultType{
    boolean is_bst;
    int minValue, maxValue;
    ResultType(boolean is_bst, int minValue, int maxValue) {
        this.is_bst = is_bst;
        this.minValue = minValue;
        this.maxValue = maxValue;
    }
}

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) {
        ResultType r = validateHelper(root);
        return r.is_bst;
    }
    
    private ResultType validateHelper(TreeNode root) {
        // 注意此处返回值，minValue 对应 Integer.MAX_VALUE，maxValue 对应 Integer.MIN_VALUE，否则叶子结点会报错
        // 对空指针必须要有返回值，对于 root 取非 Integer.MIN_VALUE, Integer.MAX_VALUE 两个数的情况下，程序正常
        if (root == null) {
            return new ResultType(true, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }
        
        ResultType left = validateHelper(root.left);
        ResultType right = validateHelper(root.right);
        
        if (!left.is_bst || !right.is_bst) {
            return new ResultType(false, 0, 0);
        }
        
        // 如果不对 root.left 和 root.right 做非空判断，当根结点值为 Integer.MIN_VALUE, Integer.MAX_VALUE 时会因为上面对空结点的返回值出现错误判断
        if (root.left != null && left.maxValue >= root.val ||
            root.right != null && right.minValue <= root.val) {
                return new ResultType(false, 0, 0);
        }
        
        // 左右儿子是null时，返回Integer.MAX_VALUE和Integer.MIN_VALUE
        // 所以要和root.val进行比较
        // (如果左右儿子不为空其实没必要比较，但程序的必须保证鲁棒性才能运行)
        int minValue = Math.min(root.val, left.minValue);
        int maxValue = Math.max(root.val, right.maxValue);
        
        return new ResultType(true, minValue, maxValue);
    }
}

2. 第二种分治：

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) {
        return divConq(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean divConq(TreeNode root, long min, long max){
        if (root == null){
            return true;
        }

        // root值和左子树最大值，右子树最小值进行比较
        if (root.val <= min || root.val >= max){
            return false;
        }
        // 把赋值和判断都写到了一起
        return divConq(root.left, min, Math.min(max, root.val)) && 
                divConq(root.right, Math.max(min, root.val), max);
    }
}

两种分治本质上没什么区别

3. 遍历
   思路
   BST 有一个性质，就是它的中序遍历是递增的，因此我们按照中序遍历的过程，判断始终是递增的，那么这就是 BST，什么样的情况是递增的，就是当前遍历的结点始终大于前一个，则递增。firstNode 用于表示是否是中序遍历的第一个结点，lastVal 表示上一个结点的值，因为第一个结点是没有前结点的，也就没有了 lastVal 与当前结点的比较。
   每一轮递归都要面临判断是否是中序遍历的第一个结点

public class Solution {
    private int lastVal = Integer.MIN_VALUE;
    private boolean firstNode = true;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        // 左子树不是 BST
        if (!isValidBST(root.left)) {
            return false;
        }
        if (!firstNode && lastVal >= root.val) {
            return false;
        }

        firstNode = false;
        lastVal = root.val;
        // 右子树不是 BST
        if (!isValidBST(root.right)) {
            return false;
        }
        return true;
    }
}