[LeetCode] 109. Convert Sorted List to Binary Search Tree

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [0]
Output: [0]

Example 4:

Input: head = [1,3]
Output: [3,1]

Constraints:

• The number of nodes in head is in the range [0, 2 * 104].
• -10^5 <= Node.val <= 10^5

有序链表转换二叉搜索树。

题目即是题意，可以跟一起做。108是从有序数组转化成BST，109是从有序链表转化成BST。区别在于108可以通过找中点的办法快速找到根节点，但是109只能通过快慢指针的办法找到根节点，思路都是递归。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public TreeNode sortedListToBST(ListNode head) {
 3         if (head == null)
 4             return null;
 5         return helper(head, null);
 6     }
 7 
 8     public TreeNode helper(ListNode head, ListNode tail) {
 9         if (head == tail)
10             return null;
11         ListNode slow = head;
12         ListNode fast = head;
13         while (fast != tail && fast.next != tail) {
14             fast = fast.next.next;
15             slow = slow.next;
16         }
17         TreeNode root = new TreeNode(slow.val);
18         root.left = helper(head, slow);
19         root.right = helper(slow.next, tail);
20         return root;
21     }
22 }

JavaScript实现

 1 /**
 2  * @param {ListNode} head
 3  * @return {TreeNode}
 4  */
 5 var sortedListToBST = function (head) {
 6     if (head === null) return null;
 7     return helper(head, null);
 8 };
 9 
10 var helper = function (head, tail) {
11     if (head === tail) return null;
12     let slow = head;
13     let fast = head;
14     while (fast !== tail && fast.next !== tail) {
15         fast = fast.next.next;
16         slow = slow.next;
17     }
18     let root = new TreeNode(slow.val);
19     root.left = helper(head, slow);
20     root.right = helper(slow.next, tail);
21     return root;
22 }

相关题目