• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode783.二叉搜索树结点最小距离|MinimumDistanceBetweenBSTNodes ...

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

Example :

Input: root = [4,2,6,1,3,null,null]
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

          4
        /   \
      2      6
     / \    
    1   3  

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.

Note:

  1. The size of the BST will be between 2 and 100.
  2. The BST is always valid, each node's value is an integer, and each node's value is different.

给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。

示例:

输入: root = [4,2,6,1,3,null,null]
输出: 1
解释:
注意,root是树结点对象(TreeNode object),而不是数组。

给定的树 [4,2,6,1,3,null,null] 可表示为下图:

          4
        /   \
      2      6
     / \    
    1   3  

最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。

注意:

  1. 二叉树的大小范围在 2 到 100
  2. 二叉树总是有效的,每个节点的值都是整数,且不重复。

Runtime: 12 ms
Memory Usage: 19 MB
 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 minDiffInBST(_ root: TreeNode?) -> Int {
16         var res:Int = Int.max
17         helper(root, Int.min, Int.max, &res)
18         return res
19     }
20     
21     func helper(_ node: TreeNode?,_ low:Int,_ high:Int,_ res:inout Int)
22     {
23         if node == nil {return}
24         if low != Int.min {res = min(res, node!.val - low)}
25         if high != Int.max {res = min(res, high - node!.val)}
26         helper(node?.left, low, node!.val, &res);
27         helper(node?.right, node!.val, high, &res);        
28     }
29 }

12ms

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

16ms

 1 class Solution {
 2     func midOrder(_ root: TreeNode?) -> [Int] {
 3         guard root != nil else {
 4             return []
 5         }
 6         return midOrder(root!.left) + [root!.val] + midOrder(root!.right)
 7     }
 8     
 9     func minDiffInBST(_ root: TreeNode?) -> Int {
10         var minDiff: Int?
11         var lhs: Int?
12         for i in midOrder(root) {
13             if lhs != nil {
14                 if minDiff == nil {
15                     minDiff = abs(lhs! - i)
16                 } else {
17                     minDiff = min(minDiff!, abs(lhs! - i))
18                 }
19             }
20             lhs = i
21         }
22         return minDiff ?? 0
23     }
24 }

24ms

 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 minDiffInBST(_ root: TreeNode?) -> Int 
16     {
17         guard let root = root else { return 0 }
18         var sum = root.val
19         var nodes = [root]
20         
21         while !nodes.isEmpty
22         {
23             var temp = [TreeNode]()
24             for i in 0...nodes.count-1
25             {
26                 let root = nodes.removeFirst()
27                 if let left = root.left
28                 {
29                     temp.append(left)
30                 }
31                 
32                 if let right = root.right
33                 {
34                     temp.append(right)
35                 }
36                 compare(root, root.val, &sum)
37             }
38             nodes = temp
39         }
40         
41         return sum
42     }
43     
44     func compare(_ root: TreeNode?, _ target: Int, _ sum: inout Int)
45     {
46         guard let root = root else { return }
47         let left = root.left
48         let right = root.right
49         if let left = left
50         {
51             sum = min(abs(target-left.val), sum)
52         }
53         
54         if let right = right
55         {
56             sum = min(abs(target-right.val), sum)
57         }
58         
59         if left != nil && right != nil
60         {
61             sum = min(abs(left!.val-right!.val), sum)
62         }
63         
64         compare(root.left, target, &sum )
65         compare(root.right, target, &sum)
66     }
67 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
iOSSwift--UIImageViewUIImage发布时间:2022-07-13
下一篇:
Swift版音乐播放器(简化版)发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap