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

进步感受：

good job！一开始就有思路，而且思路上，就一个判断的地方是错的，导致整个算法出了差错。还对官方的算法做了一个改进，官方的栈算法，多用了一个arraylist搜集所有数组，我的只要用一个pre记录前值，之后，不断跟前值判断比对就可以了！减少了时间和空间上的O(n)复杂度。

解题思路：

一、递归方法：

1、使用中序的方式遍历，整颗树，只要比较前值和当前值大小就可以，形式就是中序遍历，只是有返回值而已。

2、判断上有个小技巧是：递归的过程，有三处返回的地方，可以用if(!(xx)) { return false; } 的方式达到返回可能的所有情况。

3、中途的处理就只是判断，是否大于和前值，还有比较过后，把当前值符给pre值就可以了。

4、如果root默认就是true的，这就是到叶子节点的情况，只有自己了，当然是搜索二叉树了，也就是一个节点的二叉树也是搜索二叉树。

二、栈遍历方法：

栈遍历的方法，我是掌握了的，关键是比较的方法，就是如下：

1、 记录pre值，初始化为Integer.MIN，树遍历到第一个节点，最左节点时，它的初值就是Integer.MIN

2、使用 root.val < pre ，判断前值是否大于当前值，如果是，就不是搜索二叉树，返回false

import java.util.*;

public class Solution {
    int pre = Integer.MIN_VALUE;
    
    /** 
     * 递归方法
     */
    public boolean isValidBST (TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }
        if (root.val < pre) {
            return false;
        }
        pre = root.val;
        if (!isValidBST(root.right)) {
            return false;
        }
        return true;
    }

    /**
     * 栈遍历方法
     */
    public boolean isValidBST2 (TreeNode root) {
        if (root == null) {
            return false;
        }

        Stack<TreeNode> s = new Stack<>();
        // s.push(root); 就是这一句话导致了整个算法的失败
        // 中序遍历和后序遍历，所有的add操作都在嵌套的小while循环添加的
        // 除了这个地方，没有任何地方再添加元素了！！！
        while (root != null || !s.isEmpty()) {
            while (root != null) {
                s.push(root);
                root = root.left;
            }
            TreeNode top = s.pop();
            if(top.val < pre) {
                return false;
            } else {
                pre = top.val;
            }
            root = top.right;
        }
        return true;
    }
}