Swift 验证二叉搜索树- LeetCode
LeetCode
题目： 验证二叉搜索树
验证二叉搜索树 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例1:
输入:
2
/ \
1 3
输出: true示例2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。方案一：
- 二叉搜索树遍历后是一个有序数组
- 二叉树前序遍历并存储节点，比较前值和后值，前值比后值大则非有序
代码一：
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func isValidBST(_ root: TreeNode?) -> Bool {
guard root != nil else { return true }
var stack = [TreeNode](), node = root, pre: TreeNode? = nil
while node != nil || !stack.isEmpty {
while node != nil {
stack.append(node!)
node = node!.left
}
node = stack.removeLast()
if pre != nil && pre!.val >= node!.val {
return false;
}
pre = node
node = node!.right
}
return true
}
}方案二：
- 二叉搜索树的左节点一定小于根节点
- 二叉搜索树的右节点一定大于根节点
代码二：
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func isValidBST(_ root: TreeNode?) -> Bool {
return isValidBSTUtil(root, Int.min, Int.max);
}
func isValidBSTUtil(_ node: TreeNode?,_ min: Int,_ max: Int) -> Bool {
guard let node = node else {
return true
}
//左节点需要小于根节点值，右节点需要大于根节点
guard node.val > min && node.val < max else {
return false
}
return isValidBSTUtil(node.left, min, node.val) && isValidBSTUtil(node.right, node.val, max)
}
}对isValidBSTUtil(node.left, min, node.val) && isValidBSTUtil(node.right, node.val, max)
取一个切片：
isValidBSTUtil(node.left, min, node.val)
此时，
- 函数内的 node.val 就是 root.left.val
- 函数内的 min 就是 min
- 函数内的 max 就是 root.val
node.val < max -> root.left.val < root.val
node.val > min -> root.left.val > min取另一个一个切片：
isValidBSTUtil(node.right, node.val, max)
此时，
- 函数内的 node.val 就是 root.right.val
- 函数内的 min 就是 root.val
- 函数内的 max 就是 max
node.val < max -> root.right.val < max
node.val > min -> root.right.val > root.val 换种写法可能更好理解
//左节点需要小于根节点值，右节点需要大于根节点
guard node.val > min && node.val < max else {
return false
}
/*-------------to---------------->>>>/*
if let min = min, node.val <= min {
return false
}
if let max = max, node.val >= max {
return false
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.11.29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录