以蜿蜒形式打印二叉树的层序遍历结果

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

这个任务是否有更好的算法呢？

我的整个程序在这里

- poorvank

Answer 1

可以。

你可以执行类似于普通层序遍历的操作。

您需要使用两个栈

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

从根节点开始。将其子节点存储在一个栈中。每次迭代时，您在一个堆栈中拥有一个级别的节点。打印节点，并将下一级别的节点推入另一个堆栈中。重复此过程，直到达到最终级别。

时间复杂度为O(n)，空间复杂度为O(n)。

- banarun

---

不错的答案..通过一段时间的试错，我得出了相同的解决方案。 - ggauravr

@banarun 有没有一种方法可以在O(1)的额外空间内完成这个任务？只是好奇。 - Nikunj Banka

@NikunjBanka 我认为这是不可能的，即使你使用递归之类的东西，堆栈空间也会被使用。 - banarun

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)) 格式: 根-(左子树, 右子树)

应用伪代码：

spiralLevelOrderRecursion([1], [], 1)

（注意：本文中的html标签已被保留）

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

- user487478

Answer 3

以下代码可以完成任务：

使用的语言：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;
    }
}

- Ashish Jain

---

在 while 循环中，不要使用 true，而是使用 !queue.isEmpty()。 - Bhagwati Malav

Answer 4

我认为最简单的方法是使用两个栈，没有任何变量。

public void zigzagNew() {
    TreeNode t = this.root;
    Stack<TreeNode> cs = new Stack<>();
    Stack<TreeNode> ns = new Stack<>();
    cs.add(t);
    while(cs.isEmpty()==false || ns.isEmpty() == false) {
        while(cs.isEmpty() == false) {
            TreeNode cur = cs.pop();
            System.out.print(cur.val + " ");
            if(cur.left != null) {
                ns.push(cur.left);
            }
            if(cur.right != null) {
                ns.push(cur.right);
            }
        }
        System.out.println();
        while(ns.isEmpty()==false) {
            TreeNode cur = ns.pop();
            System.out.print(cur.val + " ");
            if(cur.right != null) {
                cs.push(cur.right);
            }
            if(cur.left != null) {
                cs.push(cur.left);
            }
        }
        System.out.println();
    }
}

- Aashu

Answer 5

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

public class ZigZagTraversal {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BinaryTree bt = new BinaryTree();
        int[] array = {2,5,1,3,11,7,8,9,4,10,6};
        /*
         *                  2
         *                 / \
         *                /   \
         *               /     \
         *              5       1
         *             / \     / \
         *            /   \   /   \
         *           3    11 7     8
         *          / \   / \
         *         9   4 10  6 
         * 
         * */
        bt=BinaryTree.buildATree(bt, array);
        //BinaryTree.inOrderTraversal(bt);
        zigZagTraversal(llForAllNodesAtEachDepth(bt));
        zigZagDisplay(bt);
    }
    public static void zigZagDisplay(BinaryTree bt){
        Stack<BinaryTree> s = new Stack<>();
        if(s.isEmpty())
            s.push(bt);
        boolean flag = true;
        while(!s.isEmpty()){
            Stack<BinaryTree> temp = new Stack<>();
            while(!s.isEmpty()){
                BinaryTree b = s.pop();
                System.out.print(b.data+" ");
                if(flag){
                    if(b.left!=null)
                        temp.push(b.left);
                    if(b.right!=null)
                        temp.push(b.right);
                }
                else{
                    if(b.right!=null)
                        temp.push(b.right);
                    if(b.left!=null)
                        temp.push(b.left);
                }
            }
            s=temp;
            flag=!flag;
        }
    }
    public static ArrayList<LinkedList<BinaryTree>> llForAllNodesAtEachDepth(BinaryTree bt){
        ArrayList<LinkedList<BinaryTree>> res = new ArrayList<LinkedList<BinaryTree>>();
        return createLlForAllNodesAtEachDepth(res,bt, 0);
    }
    public static ArrayList<LinkedList<BinaryTree>> createLlForAllNodesAtEachDepth(ArrayList<LinkedList<BinaryTree>> res, BinaryTree bt, int level){
        if(bt==null)
            return null;
        if(level==res.size()){
            LinkedList<BinaryTree> list = new LinkedList<BinaryTree>();
            list.add(bt);
            res.add(list);
            createLlForAllNodesAtEachDepth(res,bt.left,level+1);
            createLlForAllNodesAtEachDepth(res,bt.right,level+1);
        }
        else{
            res.get(level).add(bt);
            createLlForAllNodesAtEachDepth(res,bt.left,level+1);
            createLlForAllNodesAtEachDepth(res,bt.right,level+1);
        }
        return res;
    }
    public static void zigZagTraversal(ArrayList<LinkedList<BinaryTree>> res){
        boolean flag=true;
        for(int i=0;i<res.size();i++){
            LinkedList<BinaryTree> temp = res.get(i);
            if(flag){
                for(int j=0;j<temp.size();j++){
                    System.out.print(temp.get(j).data+" -> ");
                }
                flag=false;
            }
            else{
                for(int j=temp.size()-1;j>=0;j--){
                    System.out.print(temp.get(j).data+" -> ");
                }
                flag=true;
            }
            System.out.println();
        }
    }
}

- Mohit Motiani

Answer 6

// 使用两个栈的简单 C++ 代码

<pre> void zigzag(struct node *root)
         { 
            int lefttoright = 1 ;
            struct node *temp ;
            if(root == NULL)
              return ;
            stack<struct node *> current , next ,temp2 ;// temp is used to swap 
                                                         ////current and next            
            current.push(root);
            while(!current.empty())
            {temp = current.top();
             current.pop();
             cout<< temp->data << " " ;
             if(lefttoright)
             { if(temp->left)
                next.push(temp->left) ;
                if(temp->right) 
                 next.push(temp->right) ;
                 
                
                }
             else
                {if(temp->right)
                next.push(temp->right) ;
                if(temp->left) 
                 next.push(temp->left) ;
                }
             if(current.empty())  // make current as next and next  as current 
                                   //to hold next level nodes
             {lefttoright = 1-lefttoright ;
             temp2 = current ;
             current = next ;
             next = temp2 ;
             }
             
              
            }
            
        </pre>

- Awadesh