我有个问题我必须把一个曲折格式的二叉树转换成一个双链表。
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;
}
这里的时间复杂度O（n），其中n是给定的二叉树中的节点的NO。
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;
}我只想知道我的代码逻辑有什么问题。
一位朋友说上面的代码不起作用，而且是错误的。我找不到任何逻辑将失败的用例（排除空检查/空节点）
只要检查我代码的逻辑并让我知道就行了。
我的逻辑很简单：使用两个堆栈在stack1中，我总是先推左边的孩子，然后再推右边的孩子；在stack2中，我总是先推右边的孩子，然后再推左边的孩子。当stack1为非空弹出窗口时，最初加载stack1并在stack2中推送相应的右/左子节点对于上面的示例，我的堆栈状态应该类似于s1-b[2,3]t s2-b[7,6,5,4]ts1-b[8,9,10,11,12,13,14,15]tb-stack-bottom-t-stack-top。请再检查一遍谢谢。
最佳答案
算法：
使用改进的BFS算法，其中使用两个堆栈stack1来包含要从右到左访问的级别中的节点，而使用stack2来包含要从左到右访问的级别中的节点。
列表由根节点初始化，第一个级别（最接近根）存储在stack1中因此，第一个通过stack1将以适当的顺序拉动第一个关卡。
对于一般情况证明，假设stack1中的元素按正确的顺序存储，则从stack1中拉取n级的节点可确保按从右到左的顺序处理它们。对于每个这样处理的节点，子树存储在stack2中，先右后左这保证了从stack2检索到的N+1级节点列表具有从左到右的顺序while循环在n级没有更多节点时完成。此时，从stack2提取节点将按从左到右的顺序从n+1级检索所有节点。
相反，当从每个从左到右级别的stack2中提取节点时，将子节点存储在stack1中，先左后右，确保在下一次迭代中按从右到左的顺序提取它们。
所以基本上算法被证明是正确的现在，这并不能确保实现是特别是，您要将所有空指针添加到堆栈中，这意味着您将检索它们，然后尝试读取它们。