力扣 109 有序链表转换二叉搜索树

题意：给定一个拍序的list，把它转为二叉搜索树

思路：

1. 用runner记录当前遍历过的list节点
2. 统计list节点个数
3. 递归的把节点转换为二叉搜索树，具体见代码

思想：树的中序遍历

复杂度：时间O（n)，空间O(n)

class Solution {
    ListNode runner;
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null)
            return null;
        int len = 0;
        ListNode temp = head;
        while(temp != null) {
            temp = temp.next;
            len++;
        }
        runner = head;
        return build(0, len - 1); 
    }
    
    // 用start和end记录当前节点的左右边界
    TreeNode build(int start, int end) {
        if(start > end)
            return null;
        // 获取中间的节点
        int m = (end - start)/2 + start;
        // 中间节点左边的点都是左子树
        TreeNode left = build(start, m - 1);
        // 获取当前节点并前移runner
        TreeNode cur = new TreeNode(runner.val);
        cur.left = left;
        runner = runner.next;
        // 中间节点的右边都是右子树
        TreeNode right = build(m + 1, end);
        cur.right = right;
        return cur;
    }
}