algorithm - 将 Zigzag 顺序的二叉树转换为双向链表

Question

我有一个问题。我必须将锯齿形格式的二叉树转换为双向链表。

 Given BT:                 [1]          [2]                  [3]      [4]      [5]         [6]        [7]    [8]  [9] [10] [11] [12] [13] [14] [15]
ZigZag order of BT in DLL:      [1] [3] [2] [4] [5] [6] [7] [15] [14] [13] [12] [11] [10] [9] [8]    

Here is my pseudocode:

DLLNode* ConvertBTToZigZgDLL(Node* root)
{
  DLLNode* start=createDLLNode(root->data);
  DLLNode* tail=start;
  Stack<Node> stack1, stack2;
  stack1.push(root->left);
  stack1.push(root->right);
  while( !stack1.Empty() || !stack2.Empty() )
  {
     while(stack1.HasElement())
     {
       Node* temp=stack1.Pop();
       stack2.push(temp->right);
       stack2.push(temp->left);
       tail=Attach(tail,createDLLNode(temp->data));
       tail=tail->next;
     }
     while(stack2.HasElement())
     {
       Node* temp=stack2.Pop();
       stack1.push(temp->left);
       stack1.push(temp->right);
       tail=Attach(tail,createDLLNode(temp->data));
       tail=tail->next;
     }
  }
  return start;

} 这里的 TimeComplexity O(N)，其中 N 是给定二叉树中的节点数。

  DLLNode* Attach(DLLNode* source, DLLNode* dest)
  {
     source.Next=dest;
     dest.prev=source;
     return source;
  }

  DLLNode* CreateDLLNode(int data)
  {
    DLLNode* res=malloc(sizeof(struct DLLNode));
    res->data=data;
    res->prev=NULL;
    res->next=NULL;
    return res;
   }

我只想知道我的代码的逻辑有什么问题。

一位 friend 说上面的代码行不通而且是错误的。我找不到我的逻辑会失败的任何用例(排除空检查/空/空节点)

只需检查我的代码逻辑并告诉我即可。

我的逻辑很简单:使用 2 个堆栈。在 stack1 中，我总是先推左 child ，然后是右 child ，在 stack2 中，我总是先推右 child ，然后推左 child 。最初加载 stack1，而 stack1 是非空 pop，并将相应的右/左子节点压入 stack2。对于上面的例子，我的堆栈状态应该像 s1-B[2,3]T s2-B[7,6,5,4]T s1-B[8,9,10,11,12,13,14, 15]T B-stack 底部 T-Stack 顶部。请再次检查。谢谢。

Answer 1

算法:

使用修改后的 BFS 算法，其中使用两个堆栈而不是单个 fifo 队列 stack1 用于包含要从右到左访问的级别中的节点，而 stack2 包含要从左到右访问的节点。

列表用根节点初始化，第一层(最接近根节点)存储在stack1中。因此，第一次通过 stack1 将以适当的顺序拉取第一层。

对于一般情况证明，假设 stack1 中的元素以正确的顺序存储，从 stack1 中拉出节点 N 确保它们被处理从右到左的顺序。对于每个如此处理的节点，子树先右后左地存储在 stack2 中。这保证了从 stack2 中为第 N+1 层检索的节点列表具有从左到右的顺序。当第 N 层不再有节点时，while 循环完成。此时从 stack2 中提取节点将以 left-to 检索第 N+1 层的所有节点-正确的顺序。

相反，从左到右的每一层从stack2中拉取节点时，将stack1中的子节点先左后右存储，确保当它们是在下一次迭代中以从右到左的顺序拉出。

所以基本上该算法被证明是合理的。现在这并不能确保实现。特别是，您将所有 NULL 指针添加到堆栈，这意味着您将检索它们，然后尝试读取它们。