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, Sep 10 '20 at 10:52
BTW, [use nullptr for pointers](https://stackoverflow.com/questions/20509734/null-vs-nullptr-why-was-it-replaced) — Krzysztof Mochocki, Sep 10 '20 at 10:55
@molbdnilo but since I'm passing the pointer to the nodes aren't they being passed by reference? — Pranav V A, Sep 10 '20 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**` — , Sep 10 '20 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, Sep 10 '20 at 11:11
`void helper(TreeNode* node, int left, int right, vector nums) {` should be `void helper(TreeNode* & node, int left, int right, vector nums) {` — drescherjm, Sep 10 '20 at 11:18
pointers aren't special, you can pass them by value or by reference with the usual implications — 463035818_is_not_an_ai, Sep 10 '20 at 11:19
The `nums` parameter of helperr you may want to make that a const reference instead of pass by value (meaning copying the entire vector for each recursive call) — drescherjm, Sep 10 '20 at 11:31

score 1 · Answer 1 · answered Sep 10 '20 at 12:56

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;
    }
};

Leetcode 108. Convert Sorted Array to Binary Search Tree

1 Answers1