C++:复制具有加倍节点的二叉树

Question

目标是创建一棵树的拷贝，其中每个节点的值都是原始节点值的两倍。该函数应该递归地实现。我写了一些创建新树的代码，但错误是我的代码从未创建“完整拷贝”，它总是只有前两个级别。

Node* doubleUp(Node* root) {
int value = root->data;
Node* newroot = new Node(value*2);

if(root->left != NULL)
{
    int value = (root->left)->data;
    Node* left = new Node(value*2);
    newroot->left = left;
    doubleUp(newroot->left);
}
if(root->right != NULL)
{
    int value = (root->right)->data;
    Node* right = new Node(value*2);
    newroot->right = right;
    doubleUp(newroot->right);
}
return newroot;
}

我明白为什么要这样做，该函数总是创建一个“newroot”，而不是在第一级之后它应该只接受传递给它的参数。但不确定如何修复它。

这是一个示例树，使用了 Node 结构。

Node a(0), b(4), c(2), d(1), e(5), f(6), g(3), h(7);
a.left=&b;
a.right=&c;
c.left=&f;
b.left=&d;
b.right=&e;
d.left=&g;
d.right=&h;

Answer 1

你没有对左右子树的 doubleUp 的返回值做任何事情，所以你的递归是错误的。(你的调用实际上是在泄漏内存!)你真正想做的是这样的:

Node* doubleUp(Node* root) {
    Node* doubledRoot = new Node(root->data * 2);
    if (root->left) {
         newRoot->left = doubleUp(root->left);
    }
    if (root->left) {
         newRoot->right = doubleUp(root->right);
    }
    return doubledRoot;
}

请记住，我还没有实际测试过这段代码，因此它可能会出现轻微问题，但应该传达了基本思想。