头指针不包含二叉树中的子节点

Question

我正在复制一棵二叉树，我遇到了一个问题，我的新树的根指针最终只包含要复制的第一个节点，没有其他节点。我认为这个问题与以下事实有关：当我在辅助函数的递归中传递指针时，出于某种原因，它们没有被重新分配给新的节点内存地址。就像在 helper(t1->left, t2->left) t2->left 中一样，它实际上永远不会成为我想要的值，它保持为空。

   bool first_time = true;
   TreeNode* ref = NULL;
    void helper(TreeNode* t1, TreeNode* t2) {
        if(t1) {
            t2 = new TreeNode(t1->val);
            if(first_time) {
                ref = t2;
                first_time = false;
            }
            helper(t1->left, t2->left);
            helper(t1->right, t2->right);
        }
        
    }
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        TreeNode* tree1 = new TreeNode(1);
        tree1->left = new TreeNode(2);
        tree1->right = new TreeNode(3);
        helper(tree1, NULL);
        return ref;
    }

Answer 1

检查您的全局变量 first_time 和 ref。

if (first_time) {
  ref = t2;           // global
  first_time = false; // global set to never go here again
}

这实际上是您问题的根源 - 一旦您将第一个节点传递给您的函数，您就更改了其他全局变量 ref 并且之后永远不会在任何地方更改它。所以，基本上，在每次递归调用中，你都会用悬空指针泄漏内存。可能，您应该将参数 first_time 传递给您的函数，并且可能将 ref 作为可分配的参数传递

Answer 2

你这里有几个问题。

首先，ref 和 first_time 是严重的缺陷，您应该避免编写具有这种全局状态的代码。它不可重入，也不是 thread-safe.

其次，您正在尝试写入 t2 指针并将调用者的指针更改为该值。但是，您传递的是 t2 的副本，因此写入它的内容将会丢失。

清理它并不需要太多，只需更改您的函数以获取对指针的引用并写入 t2 将持久返回给调用者。注意，t2 是一个“out”参数，因此初始调用者将通过此指针获得树副本returned。

这是一个固定版本：

void helper(TreeNode* t1, TreeNode*& t2) {
    if(t1) {
        t2 = new TreeNode(t1->val);
        helper(t1->left, t2->left);
        helper(t1->right, t2->right);
    }  
}

这是您的测试函数的样子：

TreeNode* copyTest() {
    TreeNode* tree1 = new TreeNode(1);
    tree1->left = new TreeNode(2);
    tree1->right = new TreeNode(3);
    
    TreeNode* tree2 = nullptr;
    helper(tree1, tree2);  // tree2 is written to as new root.
    return tree2;
}

但是如果不需要out参数一般是不鼓励的

为什么不将您的 copyTree 函数写入 return 指向复制树的指针？基本上摆脱第 2 个参数，并分配当前树的副本，向下递归，将每个子副本附加到当前节点父副本，并且 return 父节点：

TreeNode* copyTree(TreeNode* tree) {
    TreeNode* ret = nullptr;
    if (tree) {
        ret = new TreeNode(tree->val);
        ret->left = copyTree(tree->left);
        ret->right = copyTree(tree->right);
    }
    return ret;
}

除非您非常小心，否则这不是防止泄漏的好方法，但它有助于理解递归和树结构。

头指针不包含二叉树中的子节点

Head pointer doesn't contain child nodes in Binary Tree

c++

binary-tree