將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。