题解 | #判断是不是二叉搜索树#

方法一

• 采用中序遍历，需要使用外部变量来记录前一个遍历的节点。

class Solution {
    boolean isBST = true; //外部变量
    TreeNode pre = null;
    public boolean isValidBST (TreeNode root) {
        // write code here
        inOrder(root);
        return isBST;
    }
    
    // 通过遍历+外部变量实现
    private void inOrder(TreeNode root){
        if(root == null)
            return;
        inOrder(root.left);
        /* 中序遍历位置 */
        if(pre != null && pre.val >= root.val){ //不是递增有序
            isBST = false;
            return;
        }
        pre = root; //当前节点中序遍历结束，变成前一个遍历的节点
        inOrder(root.right);
    }
}

方法二

• 利用左子树的最大值节点都要比根节点小，右子树的最小值节点都要比根节点大的特性。
• 记录子树的最大值与最小值节点。

class Solution {
    public boolean isValidBST (TreeNode root) {
        // write code here
        if(root == null)
            return true;
        return preOrder(root, null, null);
    }
    
    /**
    root为树的根
    min为子树的最小值节点
    max为子树的最大值节点
    满足min.val < root.val < max.val
    */
    private boolean preOrder(TreeNode root, TreeNode min, TreeNode max){
        if(root == null)
            return true;
        if(min != null && min.val >= root.val){ // 最小值大于等于子树根节点的值
            return false;
        }
        if(max != null && max.val <= root.val){ // 最大值小于等于子树根节点的值
            return false;
        }
        // 左右子树都必须满足条件
        // 左子树的最大值限定为root，右子树的最小值限定为root
        return preOrder(root.left, min, root) 
                && preOrder(root.right, root, max);
    }
}