[Swift]LeetCode109.有序链表转换二叉搜索树|ConvertSortedListtoBinarySearchTree ...

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

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

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

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

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

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

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

60ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 /**
13  * Definition for a binary tree node.
14  * public class TreeNode {
15  *     public var val: Int
16  *     public var left: TreeNode?
17  *     public var right: TreeNode?
18  *     public init(_ val: Int) {
19  *         self.val = val
20  *         self.left = nil
21  *         self.right = nil
22  *     }
23  * }
24  */
25 class Solution {
26     func sortedListToBST(_ head: ListNode?) -> TreeNode? {
27         // Count the length
28         var l = 0
29         var p = head
30         while p != nil {
31             l += 1
32             p = p?.next
33         }
34         
35         // Build an empty height balanced binary tree
36         func buildTree(_ numNodes: Int) -> TreeNode? {
37             if numNodes == 0 {
38                 return nil
39             }
40             let ret = TreeNode(0)
41             let numLeft = (numNodes - 1) / 2
42             let numRight = numNodes - 1 - numLeft
43             ret.left = buildTree(numLeft)
44             ret.right = buildTree(numRight)
45             return ret
46         }
47         let root = buildTree(l)
48         
49         // Fill the tree
50         p = head
51         func dfs(_ n: TreeNode?) {
52             guard let node = n else { return }
53             dfs(node.left)
54             node.val = p!.val
55             p = p?.next
56             dfs(node.right)
57         }
58         
59         dfs(root)
60         return root
61     }
62 }

64ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 /**
13  * Definition for a binary tree node.
14  * public class TreeNode {
15  *     public var val: Int
16  *     public var left: TreeNode?
17  *     public var right: TreeNode?
18  *     public init(_ val: Int) {
19  *         self.val = val
20  *         self.left = nil
21  *         self.right = nil
22  *     }
23  * }
24  */
25 class Solution {
26     func sortedListToBST(_ head: ListNode?) -> TreeNode? {
27         guard head != nil else { return nil }
28         var arr: [Int] = []
29         var node = head
30         while node != nil {
31             arr.append(node!.val)
32             node = node?.next
33         }
34         let mid = arr.count/2
35         let root = TreeNode(arr[mid])
36         appendBST(root, arr)
37         return root
38     }
39     
40     private func appendBST(_ root: TreeNode?, _ arr: [Int]) {
41         guard arr.count > 1, let root = root else { return }
42         let mid = arr.count/2
43         let leftArr = Array(arr[0..<mid])
44         let rightArr = Array(arr[mid+1..<arr.count])
45         if leftArr.count > 1 {
46             root.left = TreeNode(leftArr[leftArr.count/2])
47             appendBST(root.left, leftArr)
48         } else if leftArr.count == 1 {
49             root.left = TreeNode(leftArr[0])
50         }
51         if rightArr.count > 1 {
52             root.right = TreeNode(rightArr[rightArr.count/2])
53             appendBST(root.right, rightArr)
54         } else if rightArr.count == 1 {
55             root.right = TreeNode(rightArr[0])
56         }
57     }
58 }

76ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 /**
13  * Definition for a binary tree node.
14  * public class TreeNode {
15  *     public var val: Int
16  *     public var left: TreeNode?
17  *     public var right: TreeNode?
18  *     public init(_ val: Int) {
19  *         self.val = val
20  *         self.left = nil
21  *         self.right = nil
22  *     }
23  * }
24  */
25 class Solution {
26     func sortedListToBST(_ head: ListNode?) -> TreeNode? {
27         var head = head
28         if head == nil {
29             return nil
30         }
31         let len = getLength(head)
32         var h = head
33         return sortedListToBST(0, len - 1, &head)
34     }
35     private func getLength(_ head: ListNode?) -> Int {
36         var head = head
37         var len = 0
38         while head != nil {
39             len += 1
40             head = head!.next
41         }
42         return len
43     }
44     private func sortedListToBST(_ start: Int, _ end: Int, _ currNode: inout ListNode?) -> TreeNode? {
45         if start > end {
46             return nil
47         }
48         let mid = (start + end) / 2
49         let left = sortedListToBST(start, mid - 1, &currNode)
50         var root = TreeNode(currNode!.val)
51         currNode = currNode!.next
52         let right = sortedListToBST(mid + 1, end, &currNode)
53         root.left = left
54         root.right = right
55         return root
56     }
57 }

88ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 /**
13  * Definition for a binary tree node.
14  * public class TreeNode {
15  *     public var val: Int
16  *     public var left: TreeNode?
17  *     public var right: TreeNode?
18  *     public init(_ val: Int) {
19  *         self.val = val
20  *         self.left = nil
21  *         self.right = nil
22  *     }
23  * }
24  */
25 class Solution {
26     func sortedListToBST(_ head: ListNode?) -> TreeNode? {
27         if head == nil {
28             return nil
29         }
30         if head?.next == nil{
31             return TreeNode(head!.val)
32         }
33         var fast = head
34         var slow = head
35         var middle = head
36         while fast?.next != nil && fast?.next?.next != nil {
37             middle = slow
38             slow = slow?.next
39             fast = fast?.next?.next
40         }
41         fast = slow?.next
42         let root = TreeNode(slow!.val)
43         if head!.val != slow!.val {
44             middle?.next = nil
45             root.left = sortedListToBST(head)
46         }
47         root.right = sortedListToBST(fast)
48         return root
49     }
50 }

148ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 /**
13  * Definition for a binary tree node.
14  * public class TreeNode {
15  *     public var val: Int
16  *     public var left: TreeNode?
17  *     public var right: TreeNode?
18  *     public init(_ val: Int) {
19  *         self.val = val
20  *         self.left = nil
21  *         self.right = nil
22  *     }
23  * }
24  */
25 class Solution {
26     func sortedListToBST(_ head: ListNode?) -> TreeNode? {
27         var head = head
28         var array: [Int] = []
29         while head != nil {
30             array.append(head!.val)
31             head = head?.next
32         }
33         
34         return sortedArrayToBST(array)
35     }
36     
37     func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
38         guard !nums.isEmpty else {
39             return nil
40         }
41         
42         let rootIndex = nums.count/2
43         let root = TreeNode(nums[rootIndex])
44         root.left = sortedArrayToBST([Int](nums[..<rootIndex]))
45         root.right = sortedArrayToBST([Int](nums[(rootIndex+1)...]))
46         
47         return root
48     }
49 }