因为链表和array不同, 不能直接访问中间元素.
中序遍历，按照递归中序遍历的顺序对链表结点一个个进行访问，而我们要构造的二分查找树正是按照链表的顺序来的。
思路就是先对左子树进行递归，然后将当前结点作为根，迭代到下一个链表结点，最后在递归求出右子树即可。
因为listnode不能传递 所以要放入一个arraylist中
整体过程就是一次中序遍历，时间复杂度是O(n)，总的空间复杂度是栈空间O(logn)。
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
ArrayList<ListNode> res = new ArrayList<ListNode>();
res.add(head);
ListNode cur = head;
int count = 0;
while (cur != null) {
cur = cur.next;
count++;//找出链表的总个数
}
return helper(res, 0, count - 1);
}
public TreeNode helper(ArrayList<ListNode> res, int start, int end) {
if (start > end) {
return null;
}
int mid = (end + start) / 2;
TreeNode left = helper(res, start, mid - 1);
TreeNode root = new TreeNode(res.get(0).val);
root.left = left;
res.set(0, res.get(0).next);//指向链表的下一个元素 因为中序遍历 下一个要访问的点就是该点
root.right = helper(res, mid + 1, end);
return root;
}
}
第二种做法是把list存在一个hashmap里面， 然后向做arry那样的递归做， 时间复杂O（n）， 空间O(n)
public class Solution {
/**
* @param head: The first node of linked list.
* @return: a tree node
*/
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
HashMap map = new HashMap();
int i = 0;
while (head != null) {
map.put(i, head);
i++;
head = head.next;
}
return helper(0, i - 1, map);
}
public TreeNode helper(int start, int end, HashMap map) {
if (start > end) {
return null;
}
int mid = (start + end) / 2;
ListNode node = map.get(mid);
TreeNode head = new TreeNode(node.val);
head.left = helper(start, mid - 1, map);
head.right = helper(mid + 1, end, map);
return head;
}
}
