题解 | #按之字形顺序打印二叉树#

之字形打印，过程中反复的逆序打印

• 由逆序可以想到使用栈存储数据
• 由反复逆序可以使用两个栈轮流存储数据

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 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        // write code here
        ArrayList<ArrayList<Integer>> listlist = new ArrayList<ArrayList<Integer>>();
        if (pRoot == null) return listlist;
	  
        ArrayList<Integer> list = null;
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        s1.push(pRoot);

        while(!s1.isEmpty() || !s2.isEmpty())
        {
            list = new ArrayList<Integer>();
            if(!s1.isEmpty())
            {   
                while(!s1.isEmpty())
                {                    
                    TreeNode temp = s1.pop();
                    list.add(temp.val);
                    if(temp.left !=null) s2.push(temp.left);
                    if(temp.right != null) s2.push(temp.right);
                }
                listlist.add(list);
            }else
            {   
                while(!s2.isEmpty())
                {
                    TreeNode temp = s2.pop();
                    list.add(temp.val);
                    if(temp.right != null) s1.push(temp.right);
                    if(temp.left !=null) s1.push(temp.left);
                    
                }
                listlist.add(list);
            }
        }
        return listlist;
    }
}