在 C++ 中通过和 Return 'Reference to a Pointer' 进行二进制搜索树插入

Question

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode*& node = find(root, val);
        node = new TreeNode(val);
        return root;
    }
    TreeNode*& find(TreeNode*& root, int& val) {
        if (root == nullptr) return root;
        else if (root->val > val) return find(root->left, val);
        else return find(root->right, val);
    }
};

我正在学习 C++ 并在讲座幻灯片上阅读这段代码。该代码是关于将新节点插入二叉搜索树的。这个想法是找到目标位置，然后将一个新节点插入到该位置。我可以理解 'find' 函数 returning 一个 'reference to pointer' 类型的原因。我想是因为我们需要在'find'函数returns之后修改目标位置的地址。但是，我不知道为什么我们在将根节点传递给 'find' 函数时也需要使用 'reference to pointer' 类型。如果我将 TreeNode*& find(TreeNode*& root, int& val) 更改为 TreeNode*& find(TreeNode* root, int& val)，程序将 return 没有目标插入的原始树。任何人都可以帮助解决这个问题吗？提前致谢！

Answer 1

如果把find改成TreeNode*& find(TreeNode* root, int& val)然后看函数的第一行：

    if (root == nullptr) return root;

这将 return 对局部变量的引用。在 insertIntoBST 中更改它是未定义的行为，不会更改 insertIntoBST.

中的 root 变量

将第一个值插入空树时逐步查看代码：

NodeTree *tree = nullptr;
tree = insertIntoBST(tree, 42);

insertIntoBST 函数可以使用与查找和修改根相同的技巧：

void insertIntoBST(TreeNode*& root, int val) {
    TreeNode*& node = find(root, val);
    node = new TreeNode(val);
}

NodeTree *tree = nullptr;
insertIntoBST(tree, 42);
insertIntoBST(tree, 23);
insertIntoBST(tree, 666);

甚至更短：

void insertIntoBST(TreeNode*& root, int val) {
    find(root, val) = new TreeNode(val);
}

在 C++ 中通过和 Return 'Reference to a Pointer' 进行二进制搜索树插入

Pass and Return 'Reference to a Pointer' for Binary Search Tree Insertion in C++

c++

pointers

reference

binary-search-tree