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

請記住，我沒有實際測試此代碼，所以它可能會稍微打破，但仍應傳達的基本理念。

Answer 2

也許有點簡單

Node* doubleUp(Node* root) 
{ 
    if (root == nullptr) 
    return nullptr 

    Node* newroot = new Node(root->data*2); 
    newroot->left = doubleUp(root->left); 
    newroot->right = doubleUp(root->right); 

    return newroot; 
}