按之字形顺序打印二叉树

题目：

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

思路：

按之字形顺序打印二叉树需要两个栈，在打印某一个行结点时，把下一层的子结点，保存到相应的栈里。如果打印的是奇数层时（如第一层，第三层等），则先保存左子结点，再保存右子结点到第一个栈里。如果当前打印的是偶数层（第二层，第四层等），则先保存右子结点，再包存左子结点到第二栈里。

代码：

import java.util.ArrayList; import java.util.Stack; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public static ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >(); if(pRoot == null) return result; Stack<TreeNode> stack_current = new Stack<TreeNode>(); Stack<TreeNode> stack_next = new Stack<TreeNode>(); stack_current.push(pRoot); ArrayList<Integer> temp = new ArrayList<Integer>(); boolean isodd = true;//是否是奇数层 while(!stack_current.isEmpty() || !stack_next.isEmpty()){ TreeNode pNode = stack_current.pop(); temp.add(pNode.val); //System.out.println(); if(isodd){ if(pNode.left != null){ stack_next.push(pNode.left); } if(pNode.right != null){ stack_next.push(pNode.right); } }else{ if(pNode.right != null){ stack_next.push(pNode.right); } if(pNode.left != null){ stack_next.push(pNode.left); } } if(stack_current.isEmpty()){ ArrayList<Integer> temp1 = new ArrayList<Integer>(); //System.out.println(temp.size()); for(int i :temp){ temp1.add(i); } result.add(temp1); temp.clear(); Stack<TreeNode> stackTemp = new Stack<TreeNode>(); while(!stack_next.isEmpty()){ stackTemp.push(stack_next.pop()); } while(!stackTemp.isEmpty()){ stack_current.push(stackTemp.pop()); } isodd = !isodd; } } return result; } }