改变调用者传递的结构？（从前序构建二叉搜索树）

Question

我已经使用 Java 编程几年了，我正在尝试学习 C++。

我想要一些关于这段代码具体有什么问题的提示，但更重要的是，我想知道我是否正确地处理了这个问题。任务是 return TreeNode *root 到一个 BST，给定 vector<int>& preorder.

大体思路对我来说很清楚：递归地找到左右边界，并使用它构建树。

我试过：

使用 return 是 TreeNode * 的辅助方法 - 这导致 AddressSanitizer: heap-buffer-overflow 错误
将辅助方法转换为 return 类型 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

constructSubtree() 的 ptr 应该在调用之前分配，因为它没有在函数中分配。所以你应该在递归调用函数 constructSubtree() 之前分配 ptr->left 和 ptr->right。下面是工作代码（虽然不是那么整洁）

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

改变调用者传递的结构？（从前序构建二叉搜索树）

Altering a struct that has been passed by caller? (constructing binary search tree from preorder)

c++

pointers

binary-search-tree

preorder

改变调用者传递的结构？ （从前序构建二叉搜索树）

Altering a struct that has been passed by caller? (constructing binary search tree from preorder)

c++

pointers

binary-search-tree

preorder

改变调用者传递的结构？（从前序构建二叉搜索树）