题目

判断一个二叉树是否是一个有效的二叉搜索树。(为与leetCode一致，假设所有节点的关键值不重复)

解析

考察重点：二叉搜索树性质

解题方法：

方法一：

中序遍历。二叉搜索树的中序遍历结果是关键字有序的，如果结果中关键字并不是升序排列则不是二叉搜索树。不需要记录所有结果只需记录当前遍历节点关键字和前一个节点关键字，比较两者大小，如果不是升序排列即可断定不是二叉搜索树。

方法二：

递归方法。递归依次判断每个节点是否满足二叉搜索树的性质，这里，当前节点需要分别与它的左子树的最右节点和右子树的最左节点比较，观察是否符合性质，如果符合性质继续校验其他节点。因为假如右子树的最左节点不是当前节点右子树的最小节点，虽然可以通过当前节点的校验，但是在之后校验右子树其他节点时候会被发现不符合二叉搜索树的性质。

代码

方法一：

public boolean isValidBST(TreeNode root) {
    if(null == root){
        return true;
    }
    int lastValue = 0;
    //初始化标记，如果是true，则初始化lastValue，否则比较lastValue判断是否符合二叉搜索树条件
    boolean initial = true;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    //迭代中序遍历
    while(node != null){
        while(node != null){
            stack.push(node);
            node = node.left;
        }
        while(!stack.empty() && node == null){
            node = stack.pop();
            //初始化设置lastValue值
            if(initial){
                lastValue = node.val;
                initial = false;
            } else {//比较当前节点与之前值大小，如果逆序则直接判断不符合二叉搜索树性质
                if(node.val <= lastValue){
                    return false;
                } else {//更新lastValue值
                    lastValue = node.val;
                }
            }
            node = node.right;
        }
    }
    return true;
}

方法二：

public boolean isValidBST(TreeNode root) {
    if(null == root){
        return true;
    }
    //判断当前节点是否符合二叉搜索树性质
    TreeNode right = minRightChild(root.right);
    if(null != right && right.val <= root.val){
        return false;
    }
    TreeNode left = maxLeftChild(root.left);
    if(null != left && left.val >= root.val){
        return false;
    }
    //递归判断左右子树
    boolean r = isValidBST(root.right);
    boolean l = isValidBST(root.left);

    //左右子树任一不满足性质则整棵树不满足性质
    return l && r;
}

//右子树中最左节点
private TreeNode minRightChild(TreeNode right){
    if(null == right){
        return null;
    }
    while(right.left != null){
        right = right.left;
    }
    return right;
}

//左子树中最右节点
private TreeNode maxLeftChild(TreeNode left){
    if(null == left){
        return null;
    }
    while(left.right != null){
        left = left.right;
    }
    return left;
}