Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

二叉查找树的左节点值小于根节点，右节点值大于根节点。所以只需要类似二分搜索一样找到中点作为根节点的值然后在左右两边递归创建二叉树即可。 同样需要注意细节，计算中点的时候谨防溢出。

public TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}

private TreeNode build(int[] a, int start, int end) {
    if (start > end) {
        return null;
    }
    int mid = start + (end - start) / 2;
    TreeNode node = new TreeNode(a[mid]);
    node.left = build(a, start, mid - 1);
    node.right = build(a, mid + 1, end);
    return node;
}

Convert Sorted List to Binary Search Tree

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

通过链表构建二叉查找树的难点是无法快递取中点。只能先计算长度，然后从bottm-up用类似前序遍历一样来创建二叉树

public TreeNode sortedListToBST(ListNode head) {
    current = head;
    int size = getSize(head);
    return build(0, size - 1);
}

private ListNode current;

private int getSize(ListNode head) {
    int size = 0;
    while (head != null) {
        size++;
        head = head.next;
    }
    return size;
}

private TreeNode build(int start, int end) {
    if (start > end) {
        return null;
    }
    int mid = start + (end - start) / 2;
    TreeNode left = build(start, mid - 1);
    TreeNode root = new TreeNode(current.val);
    current = current.next;
    TreeNode right = build(mid + 1, end);

    root.left = left;
    root.right = right;
    return root;
}