通过并返回指针＆＃x27;对于C＆＃x2B;＆＃x2B;中的二进制搜索树插入

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 ++，并在演讲幻灯片上阅读此代码。该代码是关于将新节点插入二进制搜索树中的。这个想法是找到目标位置，然后将新节点插入到该位置。我可以理解“查找”函数返回“指针”类型的原因。我认为这是因为我们需要修改“查找”功能返回后目标位置的地址。但是，当我们将根节点传递到“查找”函数中时，我不知道为什么还需要使用“对指针的引用”类型。如果我更改treenode*＆amp;找到（treenode*＆amp; root，int＆amp; val）到treenode*＆amp;查找（treenode* root，int＆amp; val），程序将返回原始树而无需目标插入。谁能帮忙这个问题？先感谢您！

Answer 1

如果您将更改为 treenode*＆amp;查找（treenode* root，int＆amp; val）然后查看函数的第一行：

    if (root == nullptr) return root;

这将返回对本地变量的引用。在insertIntObst中更改它是未定义的行为，不会更改root actiber actertintobst 。

将第一个值插入空树时逐步浏览代码：

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

---

insertintObst函数可以使用与查找的技巧相同的技巧，并修改root到位：

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