按之字形顺序打印二叉树

题目

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

分析

　　使用两个栈去实现。奇数行使用stack1，偶数行使用stack2。

注，使用stack1时，按照左右的顺序存储；使用stack2时，按照右左的顺序存储

代码

 1     ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
 2         ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
 3         if(pRoot==null)
 4             return list;
 5         Stack<TreeNode> stack1 = new Stack<TreeNode>();
 6         Stack<TreeNode> stack2 = new Stack<TreeNode>();
 7         stack1.add(pRoot);
 8         while(!stack1.empty() || !stack2.empty()){
 9             ArrayList<Integer> li = new ArrayList<Integer>();
10             if(!stack1.empty()){
11                 while(!stack1.empty()){
12                     TreeNode node = stack1.pop();
13                     li.add(node.val);
14                     if(node.left!=null)
15                         stack2.add(node.left);
16                     if(node.right!=null)
17                         stack2.add(node.right);
18                 }
19                 list.add(li);
20             }
21             else if(!stack2.empty()){
22                 while(!stack2.empty()){
23                     TreeNode node = stack2.pop();
24                     li.add(node.val);
25                     if(node.right!=null)
26                         stack1.add(node.right);
27                     if(node.left!=null)
28                         stack2.add(node.left);
29                 }
30                 list.add(li);
31             }
32         }
33         return list;
34     }