k********r
发帖数: 18 | 1 Write a method： Node* Copy(Node* root)
that takes a pointer to a Node structure as a parameter. The
Node structure contains two pointers to other Node structures. The function
should return a complete copy of the passed-in data structure.
请问是这样做吗？
typedef struct node{
int value;
struct node *child1;
struct node *child2;
}Node;
Node* Copy(Node* root){
Node *n = new Node;
Copywrapper(n, root);
return n;
}
void Copywrapper(Node* n, Node* root){
if(!root) return;
n->v |
s***e
发帖数: 793 | 2 there might be a circle in the tree structure which need to be considered.
so we might need to store the copied nodes use a hash or map
node * completecopy_help(node* root, std::map& copied){
if(!root)return null;
if(copied[root])return copied[root];
// not copied before
node * r=new node;
copied[root]=r;
r->left= completecopy_help(root->left,copied);
r->right=completecopy_help(root->right,copied);
return r;
}
node* copy(node* root){
std::map |
k********r
发帖数: 18 | 3 3x. 树还会loop啊？
【在 s***e 的大作中提到】
: there might be a circle in the tree structure which need to be considered.
: so we might need to store the copied nodes use a hash or map
: node * completecopy_help(node* root, std::map& copied){
: if(!root)return null;
: if(copied[root])return copied[root];
: // not copied before
: node * r=new node;
: copied[root]=r;
: r->left= completecopy_help(root->left,copied);
: r->right=completecopy_help(root->right,copied);
|
k*k
发帖数: 508 | 4 I don't think so...
【在 k********r 的大作中提到】
: 3x. 树还会loop啊？
|
t****t
发帖数: 6806 | 5 如果是树,当然不会
但是问题在于,原题中有说这是树吗?
【在 k********r 的大作中提到】
: 3x. 树还会loop啊？
|
c********x
发帖数: 84 | 6 The question is to test you to write a recursive funtion. |
c****e
发帖数: 1453 | 7 Node *copy(Node *root)
{
if (root == NULL) return NULL;
Node *newnode = new Node;
newnode->value = root->value;
newnode->child1=copy(root->child1);
newnode->child2=copy(root->child2);
return newnode;
} |
c********x
发帖数: 84 | 8
very nice.
【在 c****e 的大作中提到】
: Node *copy(Node *root)
: {
: if (root == NULL) return NULL;
: Node *newnode = new Node;
: newnode->value = root->value;
: newnode->child1=copy(root->child1);
: newnode->child2=copy(root->child2);
: return newnode;
: }
|
d*******d
发帖数: 2050 | 9 DFS,BFS都可以.
function
【在 k********r 的大作中提到】
: Write a method： Node* Copy(Node* root)
: that takes a pointer to a Node structure as a parameter. The
: Node structure contains two pointers to other Node structures. The function
: should return a complete copy of the passed-in data structure.
: 请问是这样做吗？
: typedef struct node{
: int value;
: struct node *child1;
: struct node *child2;
: }Node;
|
w**i
发帖数: 48 | 10 原题中根本就没有提要copy的是什么data structure
原题:
Write a method that takes a pointer to a Node structure as a parameter. The
Node structure contains two pointers to other Node structures. The function
should return a complete copy of the passed-in data structure.
For example, the method signature could look like so:
Node* Copy(Node* root);
Note:
· Do not make any assumptions about the data structure – it could
be a tree, linked list, graph etc.
· Feel free to choose the language you are most comfortable wit |
l***a
发帖数: 519 | 11
neat!
in case there are loops, maybe it is better to mark the visted nodes and
check before copy.
【在 c****e 的大作中提到】
: Node *copy(Node *root)
: {
: if (root == NULL) return NULL;
: Node *newnode = new Node;
: newnode->value = root->value;
: newnode->child1=copy(root->child1);
: newnode->child2=copy(root->child2);
: return newnode;
: }
|
