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

---

解题分析及思路：

这道题考察的是二叉树的遍历，不熟悉二叉树的遍历可以查看二叉树。

这道题有关二叉搜索树

方法：分治法

本题为108. 将有序数组转换为二叉搜索树的扩展，与108题有所区别的是，本题的输入是一个有序链表，而108题的输入是一个有序数组。

对于有序数组，我们可以直接通过索引来访问元素，但是对于有序链表，可以使用快慢指针的方法来找到链表的中间节点。

随后，我们可以使用分治法的思想，递归地构造出二叉搜索树。

func sortedListToBST(head *ListNode) *TreeNode {
  return buildTree(head, nil)
}

func getMid(left, right *ListNode) *ListNode {
  var slow, fast = left, left
  for fast.Next != right && fast.Next.Next != right {
    slow = slow.Next
    fast = fast.Next.Next
  }
  return slow
}

func buildTree(left, right *ListNode) *TreeNode {
  if left == right {
    return nil
  }
  mid := getMid(left, right)
  node := &TreeNode{Val: mid.Val}
  node.Left = buildTree(left, mid)
  node.Right = buildTree(mid.Next, right)
  return node
}

复杂度：

• 时间复杂度：O(N)，其中 N 是树中的节点个数
• 空间复杂度：O(1)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:5.6 MB,击败了64.48% 的Go用户