二叉树的曲折方式打印级别序遍历 [英] print level order traversal of binary tree in Zigzag manner

问题描述

予有使用水平序遍历但在不同的电平螺旋形即节点应印在螺旋形式来打印的二进制树的节点

I have to print the nodes of a binary tree using level order traversal but in spiral form i.e nodes at different level should be printed in spiral form.

有关，例如：如果树是这样的：

for eg: If the tree look like:

输出应该是10 10 20 25 15 6 4。

The output should be 10 5 20 25 15 6 4.

我使用的算法很简单，就是一级序遍历的只是一个小的变化。我只是把p.if变量的变量等于1比在给定的水平左向右打印顺序，如果是-1打印从右到左。

The algorithm i used is simple and is just a small variation of level order traversal. I just took a variable p.if the variable is equal to 1 than print the order at a given level left to right , if it is -1 print right to left.

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）的情况下，歪斜树木。

I am getting the answer but the worst case complexity is probably O(n^2) in case of skewed tree.

相信没有人可以完成这个任务，更好的算法？..

Can there be a better algorithm for this task?..

我的整个计划是这里

推荐答案

是的。

您可以做类似正常水平序遍历的东西。

You can do something similar to normal level order traversal.

您必须使用两个堆栈

1. 从左至右打印一个堆栈
2. 第二组从右侧打印到左。

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

Start from the root node. Store it's children in one stack. In every iteration, you have nodes of one level in one of the stacks. Print the nodes, and push nodes of next level in other stack. Repeat until your reach the final level.

时间复杂度为O（n）和空间复杂度为O（n）。

Time Complexity O(n) and space complexity O(n).

这篇关于二叉树的曲折方式打印级别序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！