超超不会飞

0%

LeetCode98-验证二叉搜索树

Posted on Views: Valine:

题目

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

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

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 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 。

分析

二叉搜索树（Binary Search Tree）定义：

  1. 左子树上所有节点的值均小于它的根节点的值；
  2. 右子树上所有节点的值均大于它的根节点的值；
  3. Recursivly，左、右子树也分别为二叉查找树。

特点：

  1. 二叉搜索树中序遍历依次输出的值是有序的；
  2. 空树也是二叉搜索树。

解法一：中序遍历判断是否有序

根据二叉搜索树的特点，中序遍历依次遍历每个节点，会得到从小到大排好序的数组。

优化：不需要把整颗树保存在数组后，再判断是否有序，而是每次只保留前一个节点，遍历过程中比较，当前节点是否大于前一个节点。

代码如下：

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 题目中有一例测试用例小于 Integer 的最小值
    // 只能使用 double 保存前一个节点的值
    private double pre = -Double.MAX_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 左子树是否满足二叉搜索树的定义
        boolean l = isValidBST(root.left);
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 右子树是否满足二叉搜索树的定义
        boolean r = isValidBST(root.right);
        return l && r;
    }
}

复杂度分析：

  • 时间复杂度：O(N)，每个节点最多被访问一次；
  • 空间复杂度：O(N)，使用了递归，递归也可以用栈代替，每次递归都占用 1 个额外空间，最多进行 n 次递归。

解法二：递归

设计一个递归函数 helper(root, lower, upper)，root 为当前节点，lower 为当前节点的下限，upper 为当前节点的上限。

当递归左子树时，上限为父节点的值，因为左子树中任意一个节点都要小于父节点。下限不变。

当递归右子树时，下限为父节点的值，因为右子树任意一个节点都要大于父节点。上限不变。

1
2
3
4
5
             5 (null, null)
            / \
(null, 5)  1   6 (5, null)
              / \
      (5, 6) 3   6

如上图，括号中分别表示的是该节点的上限和下限：

  • root 节点都为 null ；
  • 左节点 1 的上限为父节点的值 5，1 < 5 满足条件；
  • 右节点 6 的下限为父节点的值 5，5 < 6 满足条件；
  • 节点 6 的左孩子上限为父节点的值 6，下限不变，3 < 6 满足条件，但是 3 < 5 不满足下限条件。

代码如下：

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
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

    private boolean helper(TreeNode node, Integer lower, Integer upper) {
        if (node == null) {
            return true;
        }
        int v = node.val;
        if (lower != null && v <= lower) {
            return false;
        }
        if (upper != null && v >= upper) {
            return false;
        }
        // 如果左孩子不是二叉搜索树，返回false
        if (!helper(node.left, lower, v)) {
            return false;
        }
        // 如果右孩子不是二叉搜索树，返回false
        if (!helper(node.right, v, upper)) {
            return false;
        }
        return true;
    }
}

复杂度分析：

  • 时间复杂度：O(N)，每个节点最多访问一次；
  • 空间复杂度：O(N)，使用了递归函数，每次递归占用 1 个栈空间，最多递归 n 次。

结语

两种方法都是用了递归，理解起来比较困难。如果知道中序遍历是有序的这个特点，第一种方法就比较容易理解，前提是要先理解中序遍历。第二种方法就不是普通想想就能想到的了，这是一种代码思维，多用笔在纸上写写画画，有助于理解。

本文首发于我的个人博客 https://chaohang.top

作者张小超

转载请注明出处

欢迎关注我的微信公众号 【超超不会飞】，获取第一时间的更新。