在本章中，我们将看到使用2个堆栈的树形螺旋顺序遍历。
问题陈述：
给定二叉树的根，您需要以螺旋顺序打印节点。
考虑下面的树：
之字形顺序如下所示：
解决方案将是
A，C，B，D，E，F，G
我们可以借助2个堆栈来解决此问题。
使用2个堆栈的解决方案非常简单，如下所述：
步骤1：在S1中推送节点。
步骤2：在s2中插入根节点的子级。
步骤3：弹出s1，现在s1为空。
第4步：转到s2，开始在s2中弹出元素，然后在S1中添加其子元素。
步骤5：继续执行步骤4，直到其为空。
步骤6：现在再次从S1弹出，并将其子级插入S2。
这是一种递归。您选择一个堆栈并从中弹出，然后将其子级插入相反的堆栈中。当我们交替进行时，我们可以按螺旋顺序打印它。
让我们借助示例了解步骤：
简单来说，当您从左侧堆栈弹出元素时，将元素插入右侧堆栈，反之亦然。
考虑给定示例中的树，并考虑以下给出的2个麻袋：
首先将“ a”根节点插入堆栈1，当前节点和输出均为NULL。
现在我们将其从堆栈1中取出，我们需要在堆栈2中输入其子级。首先，将左侧的子级“ b”输入右侧，然后将右侧的子级“ c”输入堆栈，如下所示：
现在堆栈1中不再有元素，并且我们已经访问了节点“ a”的所有子节点，我们将节点“ a”写入输出数组
现在我们的堆栈1为空，我们将进入堆栈2并将第一个元素弹出到当前节点中。然后将其子级添加到堆栈1，这次不是第一个右节点，然后是左节点，如下所示：
现在没有要访问的节点，我们将在输出中写入“ e”。然后将“ b”弹出到当前节点。然后将其子代写到堆栈1中。第一个右子代和左个子代如下所示：
现在在输出数组中打印“ b”节点，并且堆栈2为空，我们将从堆栈2开始弹出。
请注意，一旦当前堆栈为空，我们如何转到备用堆栈，然后将元素插入当前未选择的其他堆栈。通过这样做，我们可以得出我们的结果。
由于所有进入堆栈1的节点都是叶节点，因此我们可以将它们直接复制到o / p数组中。
从而达到我们的结果。
最终结果将如下所示：
因此，结果。
C ++解决方案
#include <iostream>
#include <stack>
#include <map>
using namespace std;
// structure to hold binary tree node
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
void perform_zizag_traversal(Node* root)
{
if (!root)
return;
stack<Node*> currentlevel;
stack<Node*> nextlevel;
// push the root
currentlevel.push(root);
// first print left to right
// then right to left
bool direction_left_to_right = true;
while (!currentlevel.empty())
{
struct Node* temp = currentlevel.top();
currentlevel.pop();
if (temp)
{
//print the data
cout << temp->data << " ";
// fill the next level data according to
// the direction
if (direction_left_to_right)
{
if (temp->left)
nextlevel.push(temp->left);
if (temp->right)
nextlevel.push(temp->right);
}
else
{
if (temp->right)
nextlevel.push(temp->right);
if (temp->left)
nextlevel.push(temp->left);
}
}
// if the current level is empty
// change the direction and swap the node
if (currentlevel.empty())
{
//change direction
direction_left_to_right = !direction_left_to_right;
swap(currentlevel, nextlevel);
}
}
}
int main()
{
Node* root = nullptr;
/* Binary tree:
16
/ \
/ \
10 25
/ \ / \
/ \ / \
7 15 18 30
*/
root = new Node(16);
root->left = new Node(10);
root->right = new Node(25);
root->left->left = new Node(7);
root->left->right = new Node(15);
root->right->left = new Node(18);
root->right->right = new Node(30);
perform_zizag_traversal(root);
return 0;
}
输出：
16 25 10 7 15 18 30
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
