LeetCode 99 验证二叉搜索树

Ciel Yang 收录于类别练习 OJ解题报告

2020-05-05 2020-05-05 约 1517 字预计阅读 4 分钟

本题是 BST 相关的经典基础题目，需要牢牢掌握，而且解法多样，值得专门记录。

题目描述

原题链接如下： LeetCode 99 验证二叉搜索树

题目大意

标准 BST 要求左子树所有节点的数值都小于根节点，而右子树所有节点的数值都大于根节点。

输入与输出

LeetCode 的二叉树都使用统一的数组表示法：

类似中序遍历的输出结果，根节点在前，而后是左右子树的内容
为了使数组内容无歧义，只有空叶子节点或最后的节点无需显式填入 null

示例输入为：

1
2
3
4
5
Input 1:
[2, 1, 3]

Input 2:
[5, 1, 4, null, null, 3, 6]

对应的示例输出为：

1
2
3
4
5
Output 1:
true

Output 2:
false

解题思路

二叉树的遍历方法有三种，而要把合格的二叉树顺序输出，显然使用中序遍历方法最直接。当然，也可以使用前序遍历方法处理子状态，但是要注意并不是子树是 BST 就代表整个树就是 BST，子树的所有节点都要符合 BST 的大小关系。

注意：空树必定是合格的 BST。

基本中序遍历

基本的方法就是使用列表容器保存所有中序遍历的结果，然后依次检查前一个元素是否严格小于当前元素。时间复杂度是 $O(n)$。

迭代中序遍历

第一种迭代中序遍历方法在遍历之后，还要再遍历所有元素一确定相邻元素的大小关系，实际上不如再遍历的同时进行大小关系的判断，可以节省一轮遍历操作。实际要做的就是维护一个本地变量保存前驱节点的数值，而遍历时则使用栈进行辅助（和用栈把递归 dfs 转化为迭代完全一致）。时间复杂度是 $O(n)$。

递归前序遍历 1

每个子树是 BST 的充要条件是：

左子树最右节点数值小于根节点数值
右子树最左节点数值小于根节点数值
左子树是 BST
右子树是 BST

每个子树都要找到左右子树的最右和最左节点，各遍历大约 n / 2 个元素，而且要遍历 n 个子树，所以总时间复杂度为 $O(n^2)$。

递归前序遍历 2

更换思路，每个子树的数值都有确定的范围，而左子树、根节点和右子树又把这个区间划分为 3 部分：

左子树范围
根节点数值
右子树范围

这样，只要在每次的前序遍历时，根据根节点数值把当前树的区间分为两半，然后分别验证左右子树是否在这个范围内容即可。时间复杂度是 $O(n)$。

递归中序遍历

第一种前序遍历递归方法在子树的检查过程中，查询左右子树的最右和最左节点的操作有重复操作。要想避免重复检查，可以利用递归的函数栈机制，保存前驱节点指针，比较前驱节点的数值是否小于当前节点内容即可。只要时中序遍历，每次都会先递归左子树，而每个左子树最后处理的一定时它的最右节点，它就是根节点的前驱节点。而只要在类中维护一个类变量 prev，并且每个非空子树都使用根节点指针覆盖它即可保证递归过程中的前驱节点正确更新。时间复杂度是 $O(n)$。

注意：
这种前驱节点获取方法也适用于后继结点获取，只要把在遍历时先遍历右子树即可
二叉树的处理中会经常使用这一技巧

代码

基本中序遍历：

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

    private val cache = ArrayList<Int>()

    fun isValidBST(root: TreeNode?): Boolean {
        inorder(root)
        for (i in 1..cache.lastIndex) {
            if (cache[i - 1] >= cache[i]) return false
        }
        return true
    }

    private fun inorder(root: TreeNode?) {
        if (root == null) return

        inorder(root.left)
        cache.add(root.`val`)
        inorder(root.right)
    }
}

迭代中序遍历：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Stack

class Solution {
    fun isValidBST(root: TreeNode?): Boolean {
        val stack = Stack<TreeNode>()
        var node = root
        var inorder: Int? = null
        while (stack.isNotEmpty() || node != null) {
            while (node != null) {
                stack.push(node)
                node = node.left
            }
            node = stack.pop()
            if (inorder != null && node.`val` <= inorder) return false
            inorder = node.`val`
            node = node.right
        }
        return true
    }
}

递归前序遍历 1：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    fun isValidBST(root: TreeNode?): Boolean {
        if (root == null) return true
        var left: Int? = null
        var node = root.left
        while (node != null) {
            left = node.`val`
            node = node.right
        }
        var right: Int? = null
        node = root.right
        while (node != null) {
            right = node.`val`
            node = node.left
        }
        if ((left != null && left >= root.`val`) || (right != null && right <= root.`val`)) return false
        return isValidBST(root.left) && isValidBST(root.right)
    }
}

递归前序遍历 2：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    fun isValidBST(root: TreeNode?): Boolean {
        return helper(root, null, null)
    }

    private fun helper(root: TreeNode?, lowerBound: Int?, upperBound: Int?): Boolean {
        if (root == null) return true
        val value = root.`val`
        if (lowerBound != null && lowerBound >= value) return false
        if (upperBound != null && upperBound <= value) return false
        return helper(root.left, lowerBound, value) && helper(root.right, value, upperBound)
    }
}

递归中序遍历：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {

    private var prev: TreeNode? = null

    fun isValidBST(root: TreeNode?): Boolean {
        if (root == null) return true

        if (!isValidBST(root.left) || (prev != null && prev!!.`val` >= root.`val`)) return false
        prev = root
        return isValidBST(root.right)
    }
}

目录