Leetcode 109: 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.

 

 这个题目一开始直接利用每次求链表中间来做，但是有的问题处理起来会比较麻烦，最后是看到网上大多数人都是先把linklist里面的数存储到一个vector里面，这样就转化为已知preorder的顺序求inorder的顺序，这样做就方便很多了。

 

特别注意： 

1. 在利用recursion做题时，对于参数中不发生改变的参数，应该要用&来修饰，这样在下一次调用的时候就不会对这个不变量再去分配空间了，不然会出现memory limit exceeds的问题。

2. 一旦声明了一个pointer，就必须当时就对Pointer进行初始化NULL， 不然返回一个没有任何指向的pointer,直接出bug。 

 

 

 

class Solution {
private:
    TreeNode* helper( vector<int> &buf, int left, int right) {
        //base case
        if (left > right) return NULL;
        int mid = left + (right-left)/2;
        TreeNode* rst = new TreeNode(buf[mid]);
        rst->left = helper( buf, left, mid-1);
        rst->right =helper( buf, mid+1, right);
        return rst;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        TreeNode* rst = NULL;
        if (head == NULL) return rst;
        vector<int> buf;
        while (head) {
            buf.push_back(head->val);
            head = head->next;
        }
        return helper(buf, 0, buf.size()-1);
        //return rst;
    }
};