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 < max -> root.left.val < root.val
node.val > min -> root.left.val > min
取另一个一个切片:
isValidBSTUtil(node.right, node.val, 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
}