Java日记2018-05-08

第一题 按之字形顺序打印二叉树
实现方法是采用两个栈，首先将根节点放入栈s1，然后偶数层从右往左插入，奇数层从左往右，所以要定义一个层数layer。因为栈的后入先出的特点，奇数层先保存右树，后保存左树，偶数层相反

public static ArrayList<ArrayList<Integer>> zhiZiPrint(TreeNode pnode) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        //存放奇数层
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        //存放偶数层
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        //初始化层数
        int layer =1;
        //初始化层1
        s1.push(pnode);
        while(!s1.isEmpty() || !s2.empty()) {
            if(layer%2==1) {
                //奇数层
                ArrayList<Integer> temp =new  ArrayList<Integer>();

                while(!s1.empty()){
                    TreeNode node = s1.pop();
                    if(node!=null) {
                         temp.add(node.val);
                        System.out.print(node.val + " ");
                        s2.push(node.right);
                        s2.push(node.left);
                    }
                }
                if(!temp.isEmpty()){
                    layer++;
                    list.add(temp);
                }
                
                
            } else {
                ArrayList<Integer> temp =new  ArrayList<Integer>();

                while(!s1.empty()){
                    TreeNode node = s1.pop();
                    if(node!=null) {
                        temp.add(node.val);
                        System.out.print(node.val + " ");
                        s2.push(node.right);
                        s2.push(node.left);
                    }
                }
                if(!temp.isEmpty()){
                    layer++;
                    list.add(temp);
                }
                
            }
        }
        
        
        return list;
    }