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.

Answer 1

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