剑指offer——按之字型打印二叉树

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

解题思路：

之字形用栈！！

 1 import java.util.ArrayList;
 2 
 3 /*
 4 public class TreeNode {
 5     int val = 0;
 6     TreeNode left = null;
 7     TreeNode right = null;
 8 
 9     public TreeNode(int val) {
10         this.val = val;
11 
12     }
13 
14 }
15 */
16 import java.util.*;
17 public class Solution {
18     public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
19         
20         int level=1;
21         ArrayList<ArrayList<Integer>> res = new ArrayList<>();
22         
23         Stack<TreeNode> s1 = new Stack<>();
24         Stack<TreeNode> s2 = new Stack<>();
25         if(pRoot==null)
26             return res;
27         s1.push(pRoot);
28         while(!s1.isEmpty()||!s2.isEmpty())
29         {
30             if(level%2!=0)
31             {
32                 ArrayList<Integer> list = new ArrayList<>(); 
33                 while(!s1.isEmpty())
34                 {
35                     TreeNode node = s1.pop();
36                     if(node!=null)
37                     {
38                         list.add(node.val);
39                         s2.push(node.left);
40                         s2.push(node.right);
41                     }
42                 }
43                 if(!list.isEmpty())
44                 {
45                     res.add(list);
46                     level++;
47                 }
48             }
49             
50             if(level%2==0)
51             {
52                 ArrayList<Integer> list = new ArrayList<>(); 
53                 while(!s2.isEmpty())
54                 {
55                     TreeNode node = s2.pop();
56                     if(node!=null)
57                     {
58                         list.add(node.val);
59                         s1.push(node.right);
60                         s1.push(node.left);
61                     }
62                 }
63                 if(!list.isEmpty())
64                 {
65                     res.add(list);
66                     level++;
67                 }
68             }
69             
70         }
71         return res;
72 
73     }
74 
75 }