algorithm - 以 Zigzag 方式打印二叉树的层序遍历

Question

我必须使用层序遍历打印二叉树的节点，但要以螺旋形式打印，即不同层级的节点应以螺旋形式打印。

例如:如果树看起来像:

输出应该是 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

Answer 1

是的。

您可以执行类似于正常级别顺序遍历的操作。

你必须使用两个堆栈

1. 第一叠打印从左到右
2. 第二叠用于从右到左打印。

从根节点开始。将它的子项存储在一个堆栈中。在每次迭代中，您在其中一个堆栈中有一个级别的节点。打印节点，并将下一级节点压入其他堆栈。重复直到你达到最终水平。

时间复杂度 O(n) 和空间复杂度 O(n)。