Nil's Blog +

LeetCode 98 验证二叉搜索树 [Swift]

题目

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

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

示例 1:

输入:

    2
   / \
  1   3

输出: true

示例 2:

输入:

    5
   / \
  1   4
     / \
    3   6

输出: false

解释: 输入为: [5,1,4,null,null,3,6]。   根节点的值为 5 ,但是其右子节点值为 4 。

思路

初步解题,最直接的想法是递归遍历每个节点,判断每个节点是否大于左节点的值,小于右节点的值(如果子节点存在)。

算法实现运行后,很快发现逻辑遗漏:每三个节点组成的子树可能都符合要求,但是对于根节点,右节点的左子节点可能小于根节点,举例如下:

    10
   / \
  5   15
     / \
    6   20

对比最初的思路,不难发现遗漏了一个判断条件:不仅右子结点要大于该节点,整个右子树的元素都应该大于该节点。

所以我们需要在遍历树的同时传入根节点的值,在比较时不仅比较子结点的值,同时也要与上下界的值进行比较,代码实现如下:

class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        return isValidBSTWithLowerAndUpper(root, lower: Int.min, upper: Int.max)
    }
    
    func isValidBSTWithLowerAndUpper(_ root: TreeNode?, lower : Int, upper : Int) -> Bool {
        if root == nil {
            return true
        }
        let val = root!.val
        if lower != Int.min && val <= lower {
            return false
        }
        if upper != Int.max && val >= upper {
            return false
        }
        
        if !isValidBSTWithLowerAndUpper(root?.right, lower: val, upper: upper) {
            return false
        }
        if !isValidBSTWithLowerAndUpper(root?.left, lower: lower, upper: val) {
            return false
        }
        return true
    }
}

算法对每个节点进行了一次遍历,时间和空间复杂度都为 O(n)。对二叉树的遍历,采用了 “前序遍历” 的方式,我们也可以采用 “中序遍历” 对本题进行求解:利用有效二叉搜索树 “中序遍历” 的输出结果应该是升序排列的数组的特征。

技术

算法

项目