LeetCode ---- 98、验证二叉搜索树

题目链接

思路：

二叉搜索树有一个特性，当使用中序遍历来遍历二叉搜索树时，遍历结果一定是一个升序的结果

利用这个特性，改造二叉树的中序遍历即可，在中序遍历打印当前节点值时，进行与之前最后一次打印的值进行比较即可

public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode pre = null;
        while (!stack.isEmpty() || root != null) {
            if (root != null) { // 当前节点不空，入栈，转向左子树
                stack.addFirst(root);
                root = root.left;
            } else {         // 当前节点为空，栈顶元素左子树为空或已经遍历过，弹出并比较
                root = stack.removeFirst();
                if (pre != null && pre.val >= root.val) {
                    return false;
                }
                pre = root;
                root = root.right;
            }
        }
        return true;
    }
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }