[Swift]LeetCode530.二叉搜索树的最小绝对差|MinimumAbsoluteDifferenceinBST ...

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

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

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

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

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

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

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:
   1
    \
     3
    /
   2
Output:
1
Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。

示例 :

输入:

   1
    \
     3
    /
   2
输出:
1
解释:
最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

注意: 树中至少有2个节点。

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     private var array = [Int]()
16     func getMinimumDifference(_ root: TreeNode?) -> Int {
17         inOrder(root)
18         
19         var minDiff = Int.max
20         
21         for x in 0..<array.count-1 {
22             let diff = array[x+1] - array[x]
23             if diff < minDiff {
24                 minDiff = diff
25             }
26         }
27         
28         return minDiff
29     }
30     
31     private func inOrder(_ node: TreeNode?) {
32         guard let node = node else { return }
33         inOrder(node.left)
34         array.append(node.val)
35         inOrder(node.right)
36     }
37 }

48ms

 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 getMinimumDifference(_ root: TreeNode?) -> Int {
16         var res = Int.max
17         guard let root = root else { return res }
18         
19         if var left = root.left {
20             while left.right != nil {
21                 left = left.right!
22             }    
23             let diff = abs(left.val - root.val)
24             if res > diff { res = diff }
25         }
26         
27         if var right = root.right {
28             while right.left != nil {
29                 right = right.left!
30             }
31             let diff = abs(root.val - right.val)
32             if res > diff { res = diff }
33         }
34         
35         let minLeft = getMinimumDifference(root.left) 
36         if res > minLeft { res = minLeft }
37         let minRight = getMinimumDifference(root.right)
38         if res > minRight { res = minRight }
39         
40         return res
41     }
42 }

52ms

 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     
16     func getMinimumDifference(_ root: TreeNode?) -> Int {
17         var pre: Int?
18         return getMinimumDifference(root, &pre)
19     }
20 
21     func getMinimumDifference(_ root: TreeNode?, _ val: inout Int?) -> Int {
22         guard let root = root else {
23             return Int.max
24         }
25 
26         var result = getMinimumDifference(root.left, &val)
27         if let val = val {
28             result = min(result, root.val - val)
29         }
30 
31         val = root.val
32         
33         result = min(result, getMinimumDifference(root.right, &val))
34 
35         return result
36     }
37     
38 }

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 getMinimumDifference(_ root: TreeNode?) -> Int {
16         var result = Int.max
17         var pre: Int?
18         let a = getMinimumDifference(root, &pre, &result)
19         print(a)
20         return result
21     }
22     
23     func getMinimumDifference(_ root: TreeNode?, _ val: inout Int?, _ result: inout Int) -> Int {
24         guard let root = root else {
25             return result
26         }
27         
28         getMinimumDifference(root.left, &val, &result)
29         if let val = val {
30             result = min(result, root.val - val)
31         }
32         
33         val = root.val
34         getMinimumDifference(root.right, &val, &result)
35         
36         return result
37     }
38 }

92ms

 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 getMinimumDifference(_ root: TreeNode?) -> Int {
16     var set = Set<Int>.init()
17     var queue = [TreeNode]()
18     if let node = root {
19         queue.append(node)
20     }
21     while !queue.isEmpty {
22         let node = queue.first
23         queue.removeFirst()
24         set.update(with: node!.val)
25         if node!.left != nil {
26             queue.append(node!.left!)
27         }
28         if node!.right != nil {
29             queue.append(node!.right!)
30         }
31     }
32     var res = Int.max
33     let arr = set.sorted()
34     for i in 0..<arr.count-1 {
35         if abs(arr[i]-arr[i+1]) < res {
36             res = abs(arr[i]-arr[i+1])
37         }
38     }
39     return res
40 }    
41 }

92ms

 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 getMinimumDifference(_ root: TreeNode?) -> Int {
16         //中序遍历的递归方法
17         var res:Int = Int.max, pre:Int = -1
18         inOrder(root,&pre ,&res)
19         return res
20     }
21     func inOrder(_ root: TreeNode?,_ pre: inout Int,_ res: inout Int)
22     {
23         if root == nil {return}
24         inOrder(root!.left,&pre,&res)
25         if pre != -1
26         {
27             res = min(res,root!.val - pre)
28         }
29         pre = root!.val
30         inOrder(root!.right,&pre,&res)
31     }
32 }