Convert Sorted List to Binary Search Tree leetcode

因为链表和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;
    }
}