109. Convert Sorted List to Binary Search Tree

第一眼看到以为是要写红黑树或者AVL树,马上去翻阅答案才发现链表是有序的,这样的话就很容易想到思路了,以后还是要注意审题。另外本题也有许多细节要注意。

Given 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:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

 0
/ \

-3 9
/ /
-10 5

Solution

递归建树,链表的中间结点为根节点,链表左边构成根节点的左子树,右边构成根节点的右子树。

细节:

  1. head和mid可能会指向同一个结点,当head == mid时,需要特殊处理,防止Stack Overflow。

Complexity

一共LogN层,每层查找mid需要O(N), 所以时间复杂度为O(NlogN)
空间复杂度 O(1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
if(head.next == null) return new TreeNode(head.val);
ListNode mid = findMid(head);
TreeNode root = new TreeNode(mid.val);
root.left = head == mid ? null : sortedListToBST(head);
root.right = sortedListToBST(mid.next);
return root;
}
public ListNode findMid(ListNode head){
ListNode slow = head, fast = head.next, pre=null;
while(fast != null && fast.next != null){
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
if(pre != null) pre.next = null;
return slow;
}