Leetcode 108. Convert Sorted Array to Binary Search Tree

Question

My code:

class Solution {
    public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* head = NULL;
        helper(head, 0, nums.size()-1, nums);
        return head;
    }
    
    void helper(TreeNode* node, int left, int right, vector<int> nums) {
        if(left>right) 
            return ;
        int mid = (left+right)/2;
        TreeNode* temp = new TreeNode(nums[mid]);
        node = temp;
        helper(temp->left, left, mid-1, nums);
        helper(temp->right, mid+1, right, nums);
    }
};

This outputs "[]" for all cases. I saw some recursive solutions which returned a TreeNode pointer and wanted to try a different solution. What am I missing here? Thanks.

Assigning to a function’s (non-reference) argument has no effect outside that function. There is nothing special about pointers. — molbdnilo
– molbdnilo, Commented Sep 10, 2020 at 10:52
@molbdnilo but since I'm passing the pointer to the nodes aren't they being passed by reference? — Pranav V A
– Pranav V A, Commented Sep 10, 2020 at 10:59
If you want a function to change what is in an int variable, you pass a pointer to it int * . If you want a function to change what is in a TreeNode* variable, you pass it a pointer TreeNode** — user14215102
– user14215102, Commented Sep 10, 2020 at 11:06
@PranavVA You’re passing a pointer by value. If the pointer is valid you can modify the node that it points to, but you can never change which node it points to. — molbdnilo
– molbdnilo, Commented Sep 10, 2020 at 11:11

Emma Marcier · Accepted Answer · 2020-09-10 12:56:15Z

Almost there! We can use const_iterator and solve the problem with a non-void helper:

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>

using ValueType = int;
using Iterator = std::vector<ValueType>::const_iterator;

static const struct Solution {
    TreeNode* sortedArrayToBST(
        const std::vector<ValueType>& nums
    ) {
        if (nums.empty()) {
            return nullptr;
        }

        return buildBinarySearchTree(std::begin(nums), std::end(nums));
    }

    TreeNode* buildBinarySearchTree(
        const Iterator lo, 
        const Iterator hi
    ) {
        if (lo >= hi) {
            return nullptr;
        }

        Iterator mid = lo + (hi - lo) / 2;
        TreeNode* root = new TreeNode(*mid);
        root->left = buildBinarySearchTree(lo, mid);
        root->right = buildBinarySearchTree(mid + 1, hi);
        return root;
    }
};

Collectives™ on Stack Overflow

Leetcode 108. Convert Sorted Array to Binary Search Tree

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related