📑 题目：109. 有序链表转换二叉搜索树

🚀 本题 LeetCode 传送门

题目大意

将链表转化为高度平衡的二叉搜索树。高度平衡的定义：每个结点的 2 个子结点的深度不能相差超过 1 。

解题思路

思路比较简单，依次把链表的中间点作为根结点，类似二分的思想，递归排列所有结点即可。

代码

package leetcode
/**
 * 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
 * }
 */
// TreeNode define
type TreeNode struct {
 Val   int
 Left  *TreeNode
 Right *TreeNode
}
func sortedListToBST(head *ListNode) *TreeNode {
 if head == nil {
  return nil
 }
 if head != nil && head.Next == nil {
  return &TreeNode{Val: head.Val, Left: nil, Right: nil}
 }
 middleNode, preNode := middleNodeAndPreNode(head)
 if middleNode == nil {
  return nil
 }
 if preNode != nil {
  preNode.Next = nil
 }
 if middleNode == head {
  head = nil
 }
 return &TreeNode{Val: middleNode.Val, Left: sortedListToBST(head), Right: sortedListToBST(middleNode.Next)}
}
func middleNodeAndPreNode(head *ListNode) (middle *ListNode, pre *ListNode) {
 if head == nil || head.Next == nil {
  return nil, head
 }
 p1 := head
 p2 := head
 for p2.Next != nil && p2.Next.Next != nil {
  pre = p1
  p1 = p1.Next
  p2 = p2.Next.Next
 }
 return p1, pre
}