leetcode之按之字形顺序打印二叉树_之字形打印二叉树leetcode

题目：

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{1,2,3,#,#,4,5}

该二叉树之字形层序遍历的结果是

[

[1],

[3,2],

[4,5]

]

思路：比照层序遍历的方法。

        这里使用两个栈来实现存储每层节点。答案要求分层输出，是一个二维数组的形式，所以对于其中的一层来说，先利用stack1中的数据（这是上一层遍历时存到栈中的这一层的值）存到list中，然后按照层数分辨出左右子节点先后顺序，把数据存到stack2中。这一层遍历完成后，stack1中成为空的，这是将stack2和stack1互换，继续进行循环。

        外层循环条件是stack1是否为空，即判断层数，里层循环同样是stack1是否为空，但是这个意义是这一层中的节点是否为空！注意这两个意义不一样！

代码：

import java.util.*;
 
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
 
}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(pRoot == null)
            return res;
        
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        
        int layer = 0;
        stack1.push(pRoot);
        
        while(!stack1.isEmpty()){
            ArrayList<Integer> amp = new ArrayList<>();
            layer++;
            res.add(amp);
            
            while(!stack1.isEmpty()){
                TreeNode temp = stack1.pop();
                
                if(layer % 2 == 1){
                    if(temp.left != null){
                        stack2.push(temp.left);
                    }
                    if(temp.right != null){
                        stack2.push(temp.right);
                    }
                }else if(layer % 2 == 0){
                    if(temp.right != null){
                        stack2.push(temp.right);
                    }
                    if(temp.left != null){
                        stack2.push(temp.left);
                    }
                }
            }
            res.add(amp);
            
            Stack<TreeNode> s = stack2;
            stack2 = stack1;
            stack1 = s;
        }
        return res;
        
    }
 
}