Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
這題我一看到童叠，覺得跟上題(108)一樣啊模孩，就是找中間結(jié)點遞歸生成BST鉴象。于是我先用了個笨方法先用O(n)時間把list上的元素擼下來保存到nums里，跑了一下，AC了吴裤。這方法可行，但占用了O(n)空間存儲。
不好的方法
//不好的方法
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
List<Integer> list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
int[] nums = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
nums[i] = list.get(i);
}
return recursion(nums, 0, nums.length - 1);
}
private TreeNode recursion(int nums[], int left, int right) {
if (left > right) return null;
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = recursion(nums, left, mid - 1);
root.right = recursion(nums, mid + 1, right);
return root;
}
好的方法：
還是看到SOLUTIONS里的高票答案爷怀，直接構(gòu)造BST，中點用快慢指針尋找晒骇。
注意：
if (head == tail) return null;這個判斷條件不能少霉撵。while里的判斷條件可以看成一個routine了磺浙，而且是!=tail，不是null
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
return recursion(head, null);
}
private TreeNode recursion(ListNode head, ListNode tail) {
ListNode runner = head;
ListNode walker = head;
//這個return不能少
if (head == tail) return null;
//這while里的判斷條件可以看成一個routine了徒坡，而且是!=tail撕氧，不是null
while (runner.next != tail && runner.next.next != tail) {
walker = walker.next;
runner = runner.next.next;
}
TreeNode root = new TreeNode(walker.val);
root.left = recursion(head, walker);
root.right = recursion(walker.next, tail);
return root;
}
