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

Question

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

 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] 

这里是我的伪代码：

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

所有我想知道什么是错在我的代码的逻辑。

一个朋友在说上面的代码无法正常工作和错误的。我无法找到任何用例在我的逻辑会失败（不包括空检查/空/空节点）

只是检查我的代码的逻辑，让我知道。

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

Answer 1

算法：

使用修改后的BFS算法，其中一个FIFO队列，而不是两个堆叠使用stack1用于包含在那些级别的节点进行访问从右到左，而stack2包含要被访问的节点从左到右。

该列表被初始化为根节点，并且第一级（最接近根）被存储在stack1。因此，第一次通过stack1将以适当的顺序拉第一级。

对于一般情况下的证明，假设stack1中的元素以正确的顺序存储，则从N层的stack1中拉取节点可确保按从右到左的顺序处理它们。对于每个如此处理的节点，将子树存储在第一个右侧的stack2中，然后保留。这保证节点列表检索从stack2级别N + 1有从左到右的顺序。当N层没有更多节点时，while循环完成。此时，从stack2中提取节点将按从左到右的顺序从层N + 1中检索所有节点。相反，当从左到右拉动从stack2开始的节点时，首先将子节点存储在stack1左边，然后右边，确保当它们在下一次迭代中按从右到左的顺序被拉出时。

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

Answer 2

这已经覆盖了另一个问题。

见this stackoverview set of answers。