Изменение структуры, которая была передана вызывающей стороной? (построение бинарного дерева поиска по предзаказу)

Question

Я запрограммировал в Java уже несколько лет, и я пытаюсь изучать C ++.

Я хотел бы дать несколько советов о том, что конкретно не так с этим фрагментом кода, но что более важно, Я хотел бы знать, правильно ли я подхожу к этому вопросу или нет. Задача состоит в том, чтобы вернуть TreeNode *root в BST, учитывая vector<int>& preorder.

Общая идея мне ясна: рекурсивно найти левую и правую границы и построить дерево, используя это.

Я пытался:

1. , используя вспомогательный метод, который возвращает TreeNode * - это вызвало AddressSanitizer: heap-buffer-overflow ошибки

2. преобразование вспомогательного метода для возврата типа void и передачи TreeNode *ptr в качестве параметра - это вызывает runtime error: member access within null pointer of type 'TreeNode' ошибки

Мой код:

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        TreeNode* root = new TreeNode();
        constructSubtree(preorder, root, 0, preorder.size());
        return root;
    }
private:
    void constructSubtree(vector<int>& preorder, TreeNode* ptr, int start, int end) {
        if(start == -1 || start >= end) {
            return;
        }
        ptr->val = preorder[start];
        int split = -1; // first idx where preorder[idx] > preorder[start]
        for(int i = start + 1; i < end; ++i) {
            if(preorder[i] > preorder[start]) {
                split = i;
                break;
            }
        }
        constructSubtree(preorder, ptr->left, start + 1, split);
        constructSubtree(preorder, ptr->right, split, end);
    }
};

некоторые примеры ввода : [8,5,1,7,10,12]

Может кто-нибудь объяснить, что я делаю неправильно?

Как я уже сказал, я все еще изучаю C ++, и мне также очень хотелось бы услышать общие советы по работе с указателями (и кто несет ответственность за освобождение их контента).

Answer 1

ptr функции constructSubtree () должен быть выделен перед вызовом, потому что он не размещен в функции. поэтому вы должны выделить ptr-> left и ptr-> right перед рекурсивным вызовом функции constructSubtree (). ниже рабочий код (хотя и не такой аккуратный)

class   TreeNode
{
public:
    TreeNode() { val = 0; left = nullptr; right = nullptr; }
    int val;
    TreeNode    *left;
    TreeNode    *right;

    void    print()
    {
        if(left != nullptr)
            left->print();
        std::cout << val << std::endl;
        if(right != nullptr)
            right->print();
    }

    void    remove()
    {
        if(left != nullptr)
            left->remove();
        if(right != nullptr)
            right->remove();
    }
};

class Solution {
public:
    TreeNode* bstFromPreorder(std::vector<int>& preorder) {
        constructSubtree(preorder, &root, 0, preorder.size());
        return root;
    }
private:
    TreeNode    *root;
    void constructSubtree(std::vector<int>& preorder, TreeNode** ptr, int start, int end) {
        if(start == -1 || start >= end) {
            return;
        }
        *ptr = new TreeNode();
        (*ptr)->val = preorder[start];
        int split = -1; // first idx where preorder[idx] > preorder[start]
        for(int i = start + 1; i < end; ++i) {
            if(preorder[i] > preorder[start]) {
                split = i;
                break;
            }
        }
        if(split != -1)
        {
            constructSubtree(preorder, &((*ptr)->left), start + 1, split);
            constructSubtree(preorder, &((*ptr)->right), split, end);
        }
    }
};