我必须使用层序遍历打印二叉树的节点,但要以螺旋形式打印,即不同层级的节点应以螺旋形式打印。
例如:如果树看起来像:
输出应该是 10 5 20 25 15 6 4。
我使用的算法很简单,只是层序遍历的一个小变体。我只是取了一个变量 p。如果变量等于 1,则从左到右打印给定级别的顺序,如果是 -1,则从右到左打印。
void getlevel(struct node *root,int n,int p)
{
if(root==NULL)
return;
if(n==0)
{
printf("%d ",root->info);
return;
}
if(n>0)
{
if(p==1)
{
getlevel(root->left,n-1,p);
getlevel(root->right,n-1,p);
}
if(p==-1)
{
getlevel(root->right,n-1,p);
getlevel(root->left,n-1,p);
}
}
}
我得到了答案,但在倾斜树的情况下,最坏情况的复杂度可能是 O(n^2)。
这个任务有更好的算法吗?..
我的整个程序是here
最佳答案
是的。
您可以执行类似于正常级别顺序遍历的操作。
你必须使用两个堆栈
- 第一叠打印从左到右
- 第二叠用于从右到左打印。
从根节点开始。将它的子项存储在一个堆栈中。在每次迭代中,您在其中一个堆栈中有一个级别的节点。打印节点,并将下一级节点压入其他堆栈。重复直到你达到最终水平。
时间复杂度 O(n) 和空间复杂度 O(n)。
关于algorithm - 以 Zigzag 方式打印二叉树的层序遍历,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17485773/