LeetCode每日一题 之 二叉树的”之“字形打印

image

题目：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。算法地址

我感觉可以自己先做做，你说呢！！！！！！

解题思路

这个和上一道 二叉树的行数打印 很相像，只不过这道题更改了每一行的打印顺序。
给出一个树

典型二叉树
那么这道题要求的打印顺序就是，FECADHGMB
我们怎么才能按照顺序打印出来呢。如果按照上一道的单辅助队列来进行打印的话，很显然是不行的。发散思维，用栈是否可以呢。 如果用一个栈的话，拿出一个结点，放入它的左右子节点，发现不能保证层序的顺序。 例如
放入F
取出F，放入CE，E位于栈顶
取出E，放入HG，G位于栈顶
这时应该打印第二层的C，但是C现在栈低。所以没发正常的输出每层的顺序。

举个栗子🌰

如果我们使用两个栈呢？
如果使用两个栈，把左右结点放到另一个栈中，那么原有的打印顺序，就不会被破坏了。现在有两个栈AB，我们先把顶部的元素放到A中，遍历A中所有元素，把他们的子元素放到B中，再遍历B中所有元素，把他们的子元素放到A中，循环往复，直到两个栈为空。这里模拟一下打印的顺序
A：放入F B：空
A：取出F B：放入子元素CE
A：放入E的子元素GH B：取出E
A：放入C的子元素DA B：取出C
A：取出A B：放入A的子元素
A：取出D B：放入D的子元素
.........
最后我们就得到了要求的打印顺序FECADHGMB

代码

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> a =new ArrayList<>();
        if(pRoot == null){
            return a;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        int index = 0;
        stack1.push(pRoot);
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            ArrayList<Integer> b=new ArrayList<>();
            if(index % 2==0){
                while(!stack1.isEmpty()){
                    TreeNode t = stack1.pop();
                    b.add(t.val);
                    TreeNode left = t.left;
                    if(left!=null){
                        stack2.push(left);
                    }
                    TreeNode right = t.right;
                    if(right!=null){
                        stack2.push(right);
                    }
                }
                
            }else{
                while(!stack2.isEmpty()){
                    TreeNode t = stack2.pop();
                    b.add(t.val);
                   
                    TreeNode right = t.right;
                    if(right!=null){
                        stack1.push(right);
                    }
                    TreeNode left = t.left;
                    if(left!=null){
                        stack1.push(left);
                    }
                }
            }
            a.add(b);
            index++;
        }
        return a;
    }
}