Zigzag方式打印二叉树的级序遍历

Question

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

例如：如果树看起来像：

输出应为 10 5 20 25 15 6 4。

我使用的算法很简单，只是级别顺序遍历的一个小变化。我只是取了一个变量p.if变量等于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）。

这个任务能有更好的算法吗？..

我的整个程序都在这里

Answer 1

以下代码将完成此工作：

使用的语言：Java

//  Algorithm for printing nodes in Zigzag order(zigzag tree traversal)
static void zigzagTreeTraversal(Node root)
{
    int count=0,c=1,i=0;
    boolean odd=false;
    Queue<Node> queue=new LinkedList<Node>();
    Node temp = null;
    queue.add(root);
    System.out.print("Printing Tree Traversal in Zigzag form :");
    while(true)
    {
        if(queue.isEmpty())
        {
            break;
        }

        for(i=0;i<c;i++)
        {
            temp=queue.remove();
            System.out.print(", " + temp.data);
            if(odd)
            {
                if(temp.right!=null)
                {
                    queue.add(temp.right);
                    count++;
                }

                if(temp.left!=null)
                {
                    queue.add(temp.left);
                    count++;
                }

            }
            else
            {
                if(temp.left!=null)
                {
                    queue.add(temp.left);
                    count++;
                }
                if(temp.right!=null)
                {
                    queue.add(temp.right);
                    count++;
                }

            }
        }
        c=count;
        count=0;
        odd=!odd;
    }
}

Answer 2

二叉树螺旋级阶遍历的伪代码。

//Define two stacks S1, S2

//At each level,
// S1 carries the nodes to be traversed in that level
// S2 carries the child nodes of the nodes in S1

spiralLevelOrder(root) {
    S1 = new Stack()
    S2 = new Stack()
    S1.push(root)
    spiralLevelOrderRecursion(S1, S2, 1)
}

spiralLevelOrderRecursion(S1, S2, level) {
    while(S1 not empty) {
    node = S1.pop()
        visit(node)
        if (level is odd) {
            S2.push(node.rightNode)
            S2.push(node.leftNode)
        }
        else {
            S2.push(node.leftNode)
            S2.push(node.rightNode)
        }
    }
    if (S2 not empty)
        spiralLevelOrderRecursion(S2, S1, level+1)
}

示例树:1-(2-(4，5)，3-(5，6))格式:root-(leftchild，rightchild)

应用伪代码:

螺旋级序递归（[1], [], 1）

S2 - [] -> [3] -> [2, 3]
visit order : 1

螺旋级别顺序递归（[2,3]，[]，2）

S2 - [] -> [4] -> [5,4] -> [6, 5, 4] -> [7, 6, 5, 4]
visit order : 2, 3

spirallevelordercursion([7，6，5，4]，[]，3)

visit order : 7, 6, 5, 4

Answer 3

没问题.

您可以做一些类似于普通级别顺序遍历的事情。

你得用两叠

< li >从左到右打印的第一叠 < li >从右向左打印的第二叠。

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

时间复杂性O（n）和空间复杂性O（n）。