98. 验证二叉搜索树

题解：
  • 迭代 和 递归两种方法思路一样， 都是利用二叉树的中序遍历
  • 二叉搜索树的中序遍历结果，是严格升序的， 所以我们中序遍历二叉树
  • 记录前一个遍历的节点，当前节点的值 比 前一个节点小或者相等时， 不满足BST，return false。 否则继续遍历
  • 遍历完毕，没有出现不满足的情况， 则为BST
思路一：

迭代：代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

    // 迭代
    public boolean isValidBST1(TreeNode root) {

        long prev = Long.MIN_VALUE;
        Stack <TreeNode>stack = new Stack<>();
        TreeNode node = root;

        while (!stack.isEmpty() || node != null){

            while (node != null){
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();
            if (node.val <= prev) return false;
            prev = node.val;
            node = node.right;
        }
        return true;
    }
思路二：

递归: 代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    // 递归
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root){

        if (root == null) return true;

        // 访问左子树
        if (!isValidBST(root.left)) return false;

        // 访问当前节点，如果当前节点的值比前一个节点的值小， 则不满足BST, return false。 否则继续遍历
        if (prev >= root.val) return false;

        // 记录前一个节点的值
        prev = root.val;

        return isValidBST(root.right);
    }