[leetcode]Convert Sorted List to Binary Search Tree

这道题有点难。（首先这题是重新创建一个新的BST，所以就不用去想怎么在原有的list里面指针颠来倒去了。）
1.首先这道题如果O(n*logn)就很简单了。如果可以O(n)空间的话，转化成数组，就可以O(n)时间，但这就没意思了。所以答案是可以O(1)空间，O(n)时间的。
2.看过答案知道是自底向上考虑。但试了一下，生成的子树的节点个数先是少的，然后变多，然后又少（一开始1个节点的左子树，然后生成3个节点的子树时，又要生成1个节点的右子树），用循环写很不好表示状态，需要用栈来记住很多东西。
3.那么看到很多相似的步骤，就可以用递归来做，但这是个自底向上的递归，怎么做呢？看一下答案，发现有这么些规律:
4.在递归中传的都是同一个链表，只是这个链表的节点不停往前走；而真正决定性变化的是区间；
5.可以看到，每次递归调用开始时，节点指针都指向区间第一个，结束时节点的指针指向区间末尾的后一个。这个可以通过数学归纳法证明，因为一个节点时成立，且k级成立时k+1级也成立。
6.每次递归调用时，分成左右两部分，左边构造完时，正好指针指向mid，创建一下root，继续构造右部分子树。
本来想用Java写的，后来发现指针的指针Java不好写，还是C++吧，本来指针啊，树啊，就是C++好。

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        int len = 0;
        ListNode * node = head;
        while (node != NULL)
        {
            node = node->next;
            len++;
        }
        return buildTree(head, 0, len-1);
    }
    
    TreeNode *buildTree(ListNode *&node, int start, int end)
    {
        if (start > end) return NULL;
        int mid = start + (end - start) / 2;
        TreeNode *left = buildTree(node, start, mid-1);
        TreeNode *root = new TreeNode(node->val);
        root->left = left;
        node = node->next;
        root->right = buildTree(node, mid+1, end);
        return root;
    }
};