to do

1] Unique Binary Search Trees

    int numTrees(int n) {
        int dp[n+1]= {0};
        dp[0] = 1;
        
        for (int i=1; i<n+1; ++i) {
            for (int mid=1; mid<i+1; ++mid) {
                dp[i] += dp[mid-1] * dp[i-mid];
            }
        }
        return dp[n];
    }

2] Unique Binary Search Trees II

注意loop内的顺序。。memory

    vector<TreeNode*> generateR(int l, int r) {
        if (l>r) return vector<TreeNode*>{nullptr};
        vector<TreeNode*> ret;
        
        for (int mid=l; mid<r+1; ++mid) {
            vector<TreeNode*> ltrees = generateR(l, mid-1);
            vector<TreeNode*> rtrees = generateR(mid+1, r);
            for (auto l: ltrees) {
                for (auto r: rtrees) {
                    TreeNode* root = new TreeNode(mid);
                    root->left = l;
                    root->right = r;
                    ret.push_back(root);
                }
            }
        }
        return ret;
    }
    
    vector<TreeNode*> generateTrees(int n) {
        if (n<1) return vector<TreeNode*>{};
        return generateR(1, n);
    }

3] Validate Binary Search Tree

最基本的就是inorder了，但是这道正巧不允许重复。否则inorder无法detect duplicates' correctness（是吗？？如果recurse时检查呢）

    void inorder(TreeNode* root, vector<int>& record) {
        if (root->left) inorder(root->left, record);
        record.push_back(root->val);
        if (root->right) inorder(root->right, record);
    }
    
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        vector<int> record;
        inorder(root, record);
        for (auto it=record.begin()+1; it<record.end(); ++it) {
            if (*it<=*(it-1)) return false;
        }
        return true;
    }

4] Convert Sorted Array to Binary Search Tree

careful not to be off by one

    TreeNode* sortedR(vector<int>& nums, int l, int r) {
        if (l>r) return nullptr;
        
        int mid = (l+r)/2;
        TreeNode* midn = new TreeNode(nums[mid]);
        midn->left = sortedR(nums, l, mid-1);
        midn->right = sortedR(nums, mid+1, r);
        return midn;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedR(nums, 0, nums.size()-1);
    }

5] Convert Sorted List to Binary Search Tree

    TreeNode* sortedListToBST(ListNode* head) {
       if (!head) return nullptr;
       
       ListNode* prev = nullptr;
       ListNode* slow = head;
       for (ListNode *fast=head; fast->next&&fast->next->next; ) {
           prev = slow;
           slow = slow->next;
           fast = fast->next->next;
       }
       
       TreeNode* root = new TreeNode(slow->val);
       if (prev) {
           prev->next = nullptr;
           root->left = sortedListToBST(head);
       }
       if (slow->next) {
           root->right = sortedListToBST(slow->next);
       }
       
       return root;
    }