98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

示例 1：

1
2
输入：root = [2,1,3]
输出：true

示例 2：

1
2
3
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1

题解：

写法一，借助数组递归：

二叉搜索树的中序遍历是递增序列，所以只要对该二叉树进行中序遍历，然后检查其是否有序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//存储遍历后结点值的数组
private List<Integer> list = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
    traveral(root);

    for (int i = 1; i < list.size(); i++) {
        if (list.get(i) <= list.get(i - 1)) {
            return false;
        }
    }
    return true;
}

void traveral(TreeNode root) {
    if (root == null) {
        return;
    }
    traveral(root.left);
    list.add(root.val);
    traveral(root.right);

}

写法二，自身递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//存储中序遍历中前一个结点的值
//因为题目中Integer.MIN_VALUE在结点取值范围内，所以需要用Long
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
    //空树也是二叉搜索树
    if (root == null){
        return true;
    }
    //中序遍历

    //左
    if (!isValidBST(root.left)){
        //如果左子树不是二叉搜索树，直接返回false
        return false;
    }


    //中
    //判断当前节点值是否大于前一节点值
    //二叉搜索树中不能有值相同的节点，所以直接用<=进行判断不满足条件的情况
    if (root.val <= pre){
        return false;
    }
    //更新前一节点值
    pre = root.val;

    //右
    return isValidBST(root.right);

}