[Swift]LeetCode98.验证二叉搜索树|ValidateBinarySearchTree

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Example 1:

Input:
    2
   / \
  1   3
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

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

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

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

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

28ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func isValidBST(_ root: TreeNode?) -> Bool {
16         return isValidBSTRecursive(root, Int.min, Int.max)
17     }
18     
19     func isValidBSTRecursive(_ node: TreeNode?, _ min: Int, _ max: Int) -> Bool {
20         if let currentNode = node {
21             if currentNode.val < max && currentNode.val > min &&
22                 isValidBSTRecursive(currentNode.left, min, currentNode.val) &&
23                 isValidBSTRecursive(currentNode.right, currentNode.val, max) {
24                     return true
25             }   
26         } else {
27             return true
28         }
29         return false;
30     }
31 }

32ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15   func isValidBST(_ root: TreeNode?, _ lowerBound: Int? = nil, _ upperBound: Int? = nil) -> Bool {
16     guard let root = root else { return true }
17     if let upper = upperBound, root.val >= upper { return false }
18     if let lower = lowerBound, root.val <= lower { return false }
19     if let left = root.left, left.val >= root.val { return false }
20     if let right = root.right, right.val <= root.val { return false }
21     let leftUpperBound = upperBound.map { max($0, root.val) } ?? root.val
22     let rightLowerBound = lowerBound.map { min($0, root.val) } ?? root.val
23     return isValidBST(root.left, lowerBound, leftUpperBound) && isValidBST(root.right, rightLowerBound, upperBound)
24   }
25 }

36ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func isValidBST(_ root: TreeNode?) -> Bool {
16         if root == nil {return true}
17         var root = root
18         var stack = [TreeNode]()
19         var prev :TreeNode? = nil
20         while root != nil || !stack.isEmpty{
21             while root != nil {
22                 stack.append(root!)
23                 root = root?.left
24             }
25             root = stack.popLast()
26             if prev != nil && root!.val <= prev!.val {return false}
27             prev = root
28             root = root?.right
29             
30         }
31         return true
32     }
33 }

44ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func isValidBST(_ root: TreeNode?) -> Bool {
16         guard let root = root else {
17             return true
18         }
19         
20         return helper(root, Int.min, Int.max)
21         
22     }
23     
24     func helper(_ root: TreeNode?, _ min: Int, _ max: Int) -> Bool {
25         guard let root = root else {
26             return true
27         }
28         
29         if let leftVal = root.left?.val {
30             if leftVal >= root.val {
31                 return false
32             }
33         }
34         
35         if let rightVal = root.right?.val {
36             if rightVal <= root.val{
37                 return false
38             }
39         }
40         
41         if root.val <= min || root.val >= max {
42             return false
43         }
44 
45         return helper(root.left, min, root.val) && helper(root.right, root.val, max)
46     }
47 }

60ms

 1 class Solution {
 2     func isValidBST(_ root: TreeNode?) -> Bool {
 3         return _helper(root, nil ,nil)
 4     }
 5     
 6     private func _helper(_ node: TreeNode?, _ min: Int?, _ max: Int?) -> Bool {
 7       guard let node = node else {
 8         return true
 9       }
10       // 所有右子节点都必须大于根节点
11       if let min = min, node.val <= min {
12         return false
13       }
14       // 所有左子节点都必须小于根节点
15       if let max = max, node.val >= max {
16         return false
17       }
18 
19       return _helper(node.left, min, node.val) && _helper(node.right, node.val, max)
20     }
21 }

64ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func isValidBST(_ root: TreeNode?) -> Bool {
16         return isValidBSTUtil(root, min: Int.min, max: Int.max)
17     }
18     
19     func isValidBSTUtil(_ node: TreeNode?, min: Int, max: Int) -> Bool {
20         guard let node = node else { return true }
21         guard node.val > min && node.val < max else { return false }
22         return isValidBSTUtil(node.left, min: min, max: node.val) && isValidBSTUtil(node.right, min: node.val, max: max) 
23     }
24 }

84ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14  /*
15  思路:
16  1.左边子树一定小于根节点的父节点,节点层级越高,数值越大
17  2.右边子树一定大约根节点的父节点,节点层级越高,数值越小
18   */
19 class Solution {
20     func isValidBST(_ root: TreeNode?) -> Bool {
21         return isValidBST(root, Int.min, Int.max)
22     }
23     
24     func isValidBST(_ root:TreeNode?, _ min:Int, _ max:Int) -> Bool {
25         if (root == nil) {
26             return true
27         }
28         
29         if (root?.val)! <= min || (root?.val)! >= max {
30             return false
31         }
32         
33         return isValidBST(root?.left, min, (root?.val)!) && isValidBST(root?.right, (root?.val)!, max)
34     }
35 }