以Z字形方式打印二级树的顺序遍历

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).

这个任务可以有更好的算法吗？

我的整个节目都在这里

Answer 1

是.

您可以执行类似于正常级别订单遍历的操作.

你必须使用两个堆栈

1. 第一个堆栈,用于从左到右打印
2. 第二个堆栈,用于从右到左打印.

从根节点开始.将它的孩子存放在一个堆栈中.在每次迭代中,您都有一个堆栈中的一个级别的节点.打印节点,并在其他堆栈中推送下一级节点.重复,直到达到最终水平.

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

Answer 2

Psuedocode用于二叉树的螺旋级顺序遍历.

//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)

应用伪代码:

spiralLevelOrderRecursion([1],[],1)

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

spiralLevelOrderRecursion([2,3],[],2)

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

spiralLevelOrderRecursion([7,6,5,4],[],3)

visit order : 7, 6, 5, 4