LeetCode 第 109 题：“有序链表转换二叉搜索树”题解
题解地址：分治法（Python 代码、Java 代码）。
说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。
传送门：109. 有序链表转换二叉搜索树。
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0 / \-3 9 / / -10 5
分治法（Python 代码、Java 代码）
思路分析：
思路其实官方题解已经写得非常清楚了，建议看看其中的动画，生动形象。
在这里主要想说二叉树的很多问题基本上都可以通过“分而治之”的策略完成。这里首先找到单链表的中间结点，然后递归构造左子树和右子树。还有一种做法是把单链表变成有序数组，这就是 「力扣」第 108 题：将有序数组转换为二叉搜索树。
编码的细节已经体现在代码注释中。
参考代码：
Python 代码：
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
# 特判：当结点为空，或者单结点的时候的简单逻辑
if head is None:
return None
if head.next is None:
return TreeNode(head.val)
# 设置 pre 指针是为了切断单链表 mid 的前半部分
pre = None
slow = head
fast = head
# 如果写 while fast and fast.next: 后面的代码稍有不同
while fast.next and fast.next.next:
pre = slow
slow = slow.next
fast = fast.next.next
# 此时 slow 结点就位于链表的中部，
# 它的值就作为 BST 的根结点返回
root = TreeNode(slow.val)
# 因为要传入下一个递归方法，所以得先保存索引
new_head = slow.next
slow.next = None
# 当链表只有 2 个结点的时候，pre 指针此时为 None，不用递归构造左子树
if pre:
pre.next = None
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(new_head)
return root
Java 代码：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
// 特判：当结点为空，或者单结点的时候的简单逻辑
if (head == null) {
return null;
}
if (head.next == null) {
return new TreeNode(head.val);
}
// 设置 pre 指针是为了切断单链表 mid 的前半部分
ListNode pre = null;
ListNode slow = head;
ListNode fast = head;
// 如果写 while fast and fast.next: 后面的代码稍有不同
while (fast.next != null && fast.next.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
// 此时 slow 结点就位于链表的中部，
// 它的值就作为 BST 的根结点返回
TreeNode root = new TreeNode(slow.val);
// 因为要传入下一个递归方法，所以得先保存索引
ListNode newHead = slow.next;
slow.next = null;
// 当链表只有 2 个结点的时候，pre 指针此时为 null，不用递归构造左子树
if(pre != null){
pre.next = null;
root.left = sortedListToBST(head);
}
root.right = sortedListToBST(newHead);
return root;
}
}