Java描述 LeetCode，98. Validate Binary Search Tree 验证一棵二叉搜索树

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。

☘️给出一棵二叉树，验证它是不是二叉搜索树，可能是很久没有看二叉搜索树了，二叉搜索树的概念不是太清楚了。这里要强调一下，什么是二叉搜索树，对于任意一个节点它的左子树上的节点都小于根节点，右子树上的节点都大于根节点的树，就叫二叉搜索树。比如，很有迷惑性的就是下面的这棵，3 是5这个节点的右子树上的节点，但是5 < 3，它就不是二叉搜索树。

☘️递归解法很经典，我也成功没有写出来，核心问题就是，我压根就没有完全理解什么数才是二叉搜索树，以至于，我认为所有节点里面，左孩子节点的值<右孩子节点的值，就是二叉搜索树。= =||，我擦叻。上了大比当了！下面就是我写的代码。。当时还各种考虑空节点啥的，害，直到遇见上面的测试用例，我呆了。。

public boolean isValidBST(TreeNode root) {
    if (root == null) {
        return true;
    }
    if (root.left == null && root.right == null) {
        return true;
    }
    if ((root.left == null && root.right.val > root.val) || (root.right == null && root.left.val < root.val)) {
        return true;
    }
    if (root.left == null || root.right == null) {
        return false;
    }
    if (root.left.val >= root.val || root.right.val <= root.val) {
        return false;
    }

    return isValidBST(root.left) && isValidBST(root.right);
}
time complexity O(N)
space complexity O(H) H 是树高

☘️那么，我去保存根节点的最小值？然后去更新这个最小值？感觉就算写出来，复杂度也很高。然后就看了眼评论，有个人说利用中序来做，pre保存前一个值，我就想到了一个关键点：二叉搜索树的中序遍历是一个递增序列我只要利用中序遍历，然后用pre去记录上一个访问到的值，那么每次访问一个节点的时候，利用pre来比较一下，就可以保证整体有序了。于是就有了如下的代码：

public TreeNode pre = null;
public boolean isValidBST2(TreeNode root) {
    if (root == null) {
        return true;
    }
    boolean left = isValidBST2(root.left);
    if (pre != null) {
        if (root.val <= pre.val) {
            return false;
        }
    }

    pre = root;
    boolean right = isValidBST2(root.right);
    return left && right;
}

☘️要注意下，这里pre一开始写null是最好的，因为节点的值这次是int最小值，你可以用long的最小值来写，但是下次万一值是数字里面的最小值，你咋办呢= =，所以用null是最好的。

难受了！铁子。

☘️于是乎，又看了一眼答案的解法，它每向孩子节点遍历的时候就用一个范围去限定孩子节点，这样也行，于是我也采用了左开右开的区间方法去做，如下：

public boolean isValidBST3(TreeNode root) {
    return traverse(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}



public boolean traverse(TreeNode root, int lower, int upper) {
    if (root == null) {
        return true;
    }
    if (root.val <= lower || root.val >= upper) {
        return false;
    }
    return traverse(root.left, lower, root.val) && traverse(root.right, root.val, upper);
}

☘️又gg了，还是老问题，遇见int最小值的时候，比如：
☘️除了用更大的比如Long的最小值和最大值作为范围限定之外，还有好的办法吗？我想了一下，比如换成闭区间？闭区间的话，当根是最小值的时候，比如-2147483648，那么左孩子的区间就应该是[-2147483648-1]，众所周知，int的最小值不能再减1了，所以这个好像也不太行。所以暂且就用答案的方法，改成Long的最值吧。代码如下：

public boolean isValidBST3(TreeNode root) {
    return traverse(root, Long.MIN_VALUE, Long.MAX_VALUE);
}



public boolean traverse(TreeNode root, long lower, long upper) {
    if (root == null) {
        return true;
    }
    if (root.val <= lower || root.val >= upper) {
        return false;
    }
    return traverse(root.left, lower, root.val) && traverse(root.right, root.val, upper);
}

☘️延续中序递归的思想，我们写成迭代的代码：这里的迭代还是要写一下的，正好复习下中序遍历的非递归写法，不挺好的。

public boolean isValidBST4(TreeNode root) {
    Stack stack = new Stack<>();
    TreeNode cur = root;
    TreeNode pre = null;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            if (pre == null) {
                pre = cur;
            } else {
                if (pre.val >= cur.val) {
                    return false;
                } else {
                    pre = cur;
                }
            }
            cur = cur.right;
        }
    }
    return true;
}

☘️首先是二叉搜索树的定义：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

☘️其次：二叉搜索树的中序遍历结果是一个严格递增的序列。

☘️接着：节点中可能有整数的最小值在，这一点也要考虑进去。所以在对pre定初始值的时候，如果第一个节点就是整数的最小值，就gg了。