LeetCode98-验证二叉搜索树

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/validate-binary-search-tree/

中文链接：https://leetcode-cn.com/problems/validate-binary-search-tree/

题目详述

定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

示例 1:

1
2
3
4
5
输入:
    2
   / \
  1   3
输出: true

示例 2:

1
2
3
4
5
6
7
8
9
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

题目详解

方法一：直接验证。

  • 给当前树设立上限和下限（初始值为 null）。
  • 若当前结点的值小于等于下限或大于等于上限，说明不是一颗二叉搜索树。
  • 若当前结点值位于上下限区间内，再检查它的左子树和右子树是否满足要求。
  • 递归时注意上下限的更新，左子树的上限更新为当前结点值，右子树的下限更新为当前结点值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_00098 {

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    private boolean isValidBST(TreeNode root, Integer min, Integer max) {
        if (root == null) {
            return true;
        }
        if ((min != null && root.val <= min) || (max != null && root.val >= max)) {
            return false;
        }
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }
}

方法二：运用二叉搜索树的中序遍历序列是从小到大排序的。

  • 可以在进行中序遍历后检查所得到的序列是否是从小到大排序的。
  • 实际上，我们可以只用比较当前结点值与前一个结点值。
  • 在中序遍历过程中，若发现存在前一个结点值大于等于当前结点值的情况，直接返回 true 即可，不用等整个遍历过程结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_00098 {

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