题目

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

 0 / \ -3 9 / / -10 5 

题解

这道题和上一道类似,改动是把数组改成了链表。 链表求中间节点的经典方法是快慢指针,慢指针每次走一步,快指针每次都走两步，这样快指针走到链表结尾的时候，慢指针就指向中间节点。 这样就可以把问题转化为递归的子问题进行求解。

class Solution { public TreeNode sortedListToBST(ListNode head) { if (head == null) { return null; } return helper(head, null); } public TreeNode helper(ListNode head, ListNode tail) { if (head == null || head == tail) { return null; } ListNode slow = head; ListNode fast = head; while (fast.next != tail && fast.next.next != tail) { fast = fast.next.next; slow = slow.next; } TreeNode current = new TreeNode(slow.val); current.left = helper(head, slow); current.right = helper(slow.next, tail); return current; } } 

这道题目还有一个比较巧妙的办法是利用 BST 中序遍历是升序的性质，去求解，具体看代码注释。

class Solution { private ListNode node; public TreeNode sortedListToBST(ListNode head) { if (head == null) { return null; } int size = 0; ListNode runner = head; node = head; while (runner != null) { runner = runner.next; size++; } // 先计算有几个节点 return inorderHelper(0, size - 1); } public TreeNode inorderHelper(int start, int end) { if (start > end) { return null; } // 划分左右子树 int mid = start + (end - start) / 2; TreeNode left = inorderHelper(start, mid - 1); // 中序遍历 TreeNode treenode = new TreeNode(node.val); treenode.left = left; node = node.next; TreeNode right = inorderHelper(mid + 1, end); treenode.right = right; return treenode; } } 

最关键的一个步骤是node = node.next 这步的意思是基于： 在 BST 中任意子树，它的中序遍历的结果如果存在一个链表中，一定是一个升序的，可以一一对应上，所以中序遍历完（这里是构建完）一个节点链表+1。

热门阅读

• [ Leetcode ] 108. 将有序数组转换为二叉搜索树
• [ Leetcode ] 107. 二叉树的层次遍历 II
• [ Leetcode ] 105. 从前序与中序遍历序列构造二叉树
• [ Leetcode ] 106. 从中序与后序遍历序列构造二叉树 手撕代码 QQ 群：805423079， 群密码：1024