以迭代方式复制二叉树

Question

我在一次采访中被问到了这个问题,它让我付出了一份工作:P面试官问道,你将获得一棵树的根,你必须将根返回复制的树,但副本应该是以迭代的方式.我在这里粘贴我的代码,我在那里写了相同的,它工作正常.我最初使用两个堆栈来做这个,面试官说他不喜欢,然后我用以下方式做到了.面试官对我使用另一个包含指向原始和最终树的指针的结构有点不满(参考代码).

我想知道是否还有其他更好的方法吗？

struct node
{
   int data;
   struct node * left;
   struct node * right;
};

struct copynode
{
   node * original;
   node * final;
};

node * copy(node *root)
{
    stack <copynode*> s;
    copynode * temp=(copynode*)malloc(sizeof(copynode));
    temp->original=root;
    temp->final=(node *)malloc(sizeof(node));
    s.push(temp);
    while(s.empty()==false)
    {
       copynode * i;
       i=s.top();
       s.pop();
       i->final=i->original;
       if(i->original->left)
       {
          copynode *left=(copynode*)malloc(sizeof(copynode));
          left->original=i->original->left;
          left->final=(node *)malloc(sizeof(node));
          s.push(left);
       }
       if(i->original->right)
       {
          copynode *right=(copynode*)malloc(sizeof(copynode));
          right->original=i->original->right;
          right->final=(node *)malloc(sizeof(node));
          s.push(right);
       }
   }  
   return temp->final;
}

Answer 1

如果允许在每个节点中拥有父指针,则甚至不需要堆栈:

同时走原始树和您正在创建的树.如果原始树中的当前节点具有左子节点,但您正在创建的树中的节点没有,则创建它并向左下移.与正确的孩子一样.如果两种情况都不适用,请上去.

在代码(C#)中:

public static Node Clone(Node original)
{
    if (original == null)
        return null;

    var root = new Node(original.Data, null);
    var clone = root;

    while (original != null)
    {
        if (original.Left != null && clone.Left == null)
        {
            clone.Left = new Node(original.Left.Data, clone);
            original = original.Left;
            clone = clone.Left;
        }
        else if (original.Right != null && clone.Right == null)
        {
            clone.Right = new Node(original.Right.Data, clone);
            original = original.Right;
            clone = clone.Right;
        }
        else
        {
            original = original.Parent;
            clone = clone.Parent;
        }
    }

    return root;
}