My obvious divide-and-conquer in cpp


  • 0
    C

    Basic idea:
    (1) base case: length of 1 or length of 2
    (2) divide the array into two part, and generate the tree.

       class Solution {
        public:
            TreeNode* sortedListToBST(ListNode* head) {
                if (!head) return NULL;
                vector<int> arr;
                while(head != NULL) {
                    arr.push_back(head->val);
                    head = head->next;
                }
                
                return generate_tree(arr, 0, arr.size() - 1);
                
            }
            
        private:
            TreeNode* generate_tree(vector<int> &arr,int start,int end) {
                if (start ==  end) {
                    return new TreeNode(arr[start]);
                } else if (end - start == 1) {
                    TreeNode *root = new TreeNode(arr[end]);
                    root->left = new TreeNode(arr[start]);
                    return root;
                } else {
                    int length = end - start + 1;
                    int mid = start + length / 2;
                    TreeNode *root = new TreeNode(arr[mid]);
                    root->left = generate_tree(arr, start, mid - 1);
                    root->right = generate_tree(arr, mid + 1, end);
                    return root;
                }
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.