LeetCode 98 验证二叉搜索树 [Swift]
2019-10-10
题目
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
-
节点的左子树只包含小于当前节点的数。
-
节点的右子树只包含大于当前节点的数。
-
所有左子树和右子树自身必须也是二叉搜索树。
示例 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)。对二叉树的遍历，采用了 “前序遍历” 的方式，我们也可以采用 “中序遍历” 对本题进行求解：利用有效二叉搜索树 “中序遍历” 的输出结果应该是升序排列的数组的特征。