108. Convert Sorted Array to Binary Search TreeGiven an array where elements are sorted in ascending order, convert it to a height balanced BST.

S: recursion

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return getBST(nums, 0, nums.size()-1);
    }

    TreeNode* getBST(vector<int>& nums, int start, int end) {
        if(start > end) return NULL;
        int mid = start + (end - start)/2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = getBST(nums, start, mid-1);
        node->right = getBST(nums, mid+1, end);
        return node;
    }

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.

S:recursion

因为要多次用到链表长度，可以先遍历一遍存储长度避免每次都用slow-fast ponter 找中点

    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return NULL;
        ListNode* mid = breakList(head);
        TreeNode* node = new TreeNode(mid->val);
        if(head != mid) {
            node->left = sortedListToBST(head);
        }
        if(mid->next) {
            node->right = sortedListToBST(mid->next);
        }
        return node;
    }

    ListNode* breakList(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* before = head;
        while(fast && fast->next) {
            fast = fast->next->next;
            before = slow;
            slow = slow->next;
        }
        before->next = NULL;
        return slow;
    }