双栈JAVA实现
按之字形顺序打印二叉树
http://www.nowcoder.com/questionTerminal/91b69814117f4e8097390d107d2efbe0
双栈来做
1.第一个栈获取pRoot
2.出栈的时候输出,然后把左右节点分别存入栈2
3.栈2同理,把右左节点存入栈1
4.因为是交替进行无需判断深度,只需要判断某个栈为空,就运行另外一个。
public class Solution { public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> listAll = new ArrayList<>(); if (pRoot == null) return listAll; Stack<TreeNode> s1 = new Stack<>(); Stack<TreeNode> s2 = new Stack<>(); int level = 1; s1.push(pRoot); while (!s1.isEmpty() || !s2.isEmpty()) { ArrayList<Integer> list = new ArrayList<>(); if (!s1.isEmpty()) { while (!s1.isEmpty()) { TreeNode node = s1.pop(); list.add(node.val); if (node.left != null) s2.add(node.left); if (node.right != null) s2.add(node.right); } listAll.add(list); continue; } else { while (!s2.isEmpty()) { TreeNode node = s2.pop(); list.add(node.val); if (node.right != null) s1.add(node.right); if (node.left != null) s1.add(node.left); } listAll.add(list); continue; } } return listAll; } }