[Swift]LeetCode783. 二叉搜索树结点最小距离 | Minimum Distance Between BST Nodes

时间 2019-11-11 标签 swift leetcode783 leetcode 783 二叉搜索树结点最小距离 minimum distance bst nodes

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： http://www.noobyard.com/article/p-agrspdsh-me.html
➤若是连接不是山青咏芝的博客园地址，则多是爬取做者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持做者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★html

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.node

Example :git

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:github

The size of the BST will be between 2 and 100.
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的差值。

注意：app

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

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 }

12msthis

 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 }

16msspa

 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 }

24mscode

 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 }