给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
示例 1:
输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。示例 2:
输入: head = []
输出: []提示:
- head 中的节点数在[0, 2 * 10^4] 范围内
- -10^5 <= Node.val <= 10^5
解题：
func sortedListToBST(head *ListNode) *TreeNode {
if head == nil {
return nil
}
var a []int
for head != nil {
a = append(a, head.Val)
head = head.Next
}
var dfs func(nums []int) *TreeNode
dfs = func(nums []int) *TreeNode {
l := len(nums)
if l == 0 {
return nil
}
mid := l / 2
root := &TreeNode{nums[mid], nil, nil}
root.Left = dfs(nums[:mid])
root.Right = dfs(nums[mid+1:])
return root
}
return dfs(a)
}官方解法：
1.分治
func sortedListToBST(head *ListNode) *TreeNode {
return buildTree(head, nil)
}
func getMedian(left, right *ListNode) *ListNode {
fast, slow := left, left
for fast != right && fast.Next != right {
fast = fast.Next.Next
slow = slow.Next
}
return slow
}
func buildTree(left, right *ListNode) *TreeNode {
if left == right {
return nil
}
mid := getMedian(left, right)
root := &TreeNode{mid.Val, nil, nil}
root.Left = buildTree(left, mid)
root.Right = buildTree(mid.Next, right)
return root
}2.分治 + 中序遍历优化
var globalHead *ListNode
func sortedListToBST(head *ListNode) *TreeNode {
globalHead = head
length := getLength(head)
return buildTree(0, length-1)
}
func getLength(head *ListNode) int {
ret := 0
for ; head != nil; head = head.Next {
ret++
}
return ret
}
func buildTree(left, right int) *TreeNode {
if left > right {
return nil
}
mid := (left + right + 1) / 2
root := &TreeNode{}
root.Left = buildTree(left, mid-1)
root.Val = globalHead.Val
globalHead = globalHead.Next
root.Right = buildTree(mid+1, right)
return root
}