从leetcode题目“二叉搜索树中的插入操作”的两种解法看C++“指针”与“指针的指针”

最近刷到“二叉搜索树中的插入操作”这道题目，这道题目比较简单，利用递归便可以很快完成，但是利用递归方法需要注意一些细节，在此与大家分享。
首先题目规定的节点的数据结构如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

一开始，直接无脑递归，写出了如下的代码，基本思路是，根据插入值的大小与节点大小的关系递归搜索左子树或者右子树，找到合适的叶子节点后，插入新值。这里我递归的结束条件是节点是否为NULL，如果为NULL，代表找到了合适的可以插入的位置。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        nsertIntoBSTCore(root, val);
        return root;
    }
    
    //传入指针的指针，否则无法真正修改到找到的叶子节点
    void insertIntoBSTCore(TreeNode* root, int val) 
    {
        if (root == NULL) 
        {
            root = new TreeNode(val);
            return;
        }
        if (root->val < val) insertIntoBSTCore(root->right, val);
        if (root->val > val) insertIntoBSTCore(root->left, val);
    }
};

乍一看这代码，似乎没有什么问题，但是实际执行后却发现无论如何二叉树均无法被修改。问题其实出现在递归结束的操作。在递归结束的操作中，将一个新的节点指针赋值给root，这里的root虽然是一个指针，但是它也是一个实参，函数结束后，这个实参也在内存空间中消失了，所以对root进行重新赋值是没有作用的。

那么如何修改呢？一种方法是，我们不传入指针，而是传入指针的指针，这样在递归结束时，我们是针对实参指向的内存空间进行修改，代码如下：

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        insertIntoBSTCore(&root, val);
        return root;
    }
    
    //传入指针的指针，否则无法真正修改到找到的叶子节点
    void insertIntoBSTCore(TreeNode** root, int val) 
    {
        if (*root == NULL) 
        {
            *root = new TreeNode(val);
            return;
        }
        if ((*root)->val < val)
        {
            insertIntoBSTCore(&((*root)->right), val);
        }
        if ((*root)->val > val)
        {
            insertIntoBSTCore(&((*root)->left), val);
        }
    }
};

事实上，对指针的指针进行操作虽然可以解决此问题，但是操作起来比较复杂，也容易出错。还有另一种方法，可以避免这个问题，修改一下递归结束的条件即可。基本思路是，不对root重新赋值，而是对root的左节点或者右节点进行赋值，因为root的左节点和右节点分别是两个已经存在内存空间中的指针。
代码如下

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        insertIntoBSTCore(root, val);
        return root;
    }
    
    //传入指针即可
    void insertIntoBSTCore(TreeNode* root, int val) 
    {
        if (root == NULL) return;
        
        if (root->val > val && root->left == NULL)
        {
            root->left = new TreeNode(val);
            return;
        }
        if (root->val < val && root->right == NULL)
        {
            root->right = new TreeNode(val);
            return;
        }
        if (root->val > val) insertIntoBSTCore(root->left, val);
        if (root->val < val) insertIntoBSTCore(root->right, val);
    }
};