文章目录
109. 有序链表转换二叉搜索树
给定一个单链表的头节点 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
解题思路
寻找到链表的中间节点作为根节点，然后递归构建左右子树
- 每次取链表中间节点作为根节点，左右两边元素相差不会大于
1，会是平衡的 - 链表本身就是升序排序，所以构建后会是二叉搜索树，
- 综上，符合题目要求的平衡二叉搜索树要求
需要注意的是递归终止条件，链表空或者只有一个元素的时候就可以终止递，往上归了，上层用root.Left或root.Right指针接住。
Go代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedListToBST(head *ListNode) *TreeNode {
// 寻找到链表的中间节点作为根节点，然后递归构建左右子树
// 每次取链表中间节点作为根节点，左右两边元素相差不会大于1，会是平衡的
// 链表本身就是升序排序，所以构建后会是二叉搜索树，
// 综上，符合题目要求的平衡二叉搜索树要求
if head == nil {
return nil
}
if head.Next == nil {
return &TreeNode{Val:head.Val}
}
// 寻找链表中间节点
midNode := findMidNodeOfList(head)
// 构造根节点
root := &TreeNode{Val:midNode.Val}
// 切割链表为左右两部分，并递归构建左右子树
rightList := midNode.Next // 右边的链表从midNode下个节点开始，直到最后
midNode.Next = nil // rightList记录了下个链表的开始，midNode的Next可以释放了
dummy := &ListNode{}
dummy.Next = head
cur := dummy
for cur.Next != midNode{
cur = cur.Next
}
cur.Next = nil // 左边的链表head开始，到midNode为止，不包含midNode
root.Left = sortedListToBST(head)
root.Right = sortedListToBST(rightList)
return root
}
func findMidNodeOfList(head *ListNode) *ListNode {
// 经典双指针做法，快指针一次走两步，慢指针一次走一步，快指针到最后一个节点，慢指针刚好指着中间节点
slow,fast := head,head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
return slow
}
