C++ mush easier method


  • 0
    H

    As far as I am concerned, this two-pass method should be faster than those one-pass methods even though those methods do have less space complexity. This method is easier and faster because it spends O(1) time finding the new middle element. Please point it out if I am wrong.

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

Log in to reply
 

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