【剑指offer】按层和按之字打印二叉树

这是网上思路比较清晰的广度优先遍历解法。

ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>(); if(pRoot==null) return result; Queue<TreeNode> queue=new LinkedList<TreeNode>(); ArrayList<Integer> layer=new ArrayList<Integer>(); queue.add(pRoot); int start=0,end=queue.size(); while(!queue.isEmpty()){ TreeNode tmp=queue.remove(); layer.add(tmp.val); start++; if(tmp.left!=null) queue.add(tmp.left); if(tmp.right!=null) queue.add(tmp.right); if(start==end){ end=queue.size(); start=0; result.add(layer); layer=new ArrayList<Integer>(); } } return result; }

按之字形打印二叉树时，书上说的是用两个栈。但是首先想到的是偶数层用队列，奇数层用栈（根结点属于0层）。然而结果证明这种方法不行，因为在打印奇数层时它是从右至左出栈的，这时将结点的左右子结点放入下一层偶数层的队列时，顺序是右左，右右，左左，左右。即使改成先右子结点再左子结点也不行，因为右右，右左，左右，左左仍然是反的。同样，用两个队列也无法实现按之字形打印。 根据BFS可以很快写出代码：

public ArrayList<ArrayList<Integer> > print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>(); if(pRoot==null) return result; Stack<TreeNode> leftToRight=new Stack<TreeNode>(); Stack<TreeNode> rightToLeft=new Stack<TreeNode>(); ArrayList<Integer> layer=new ArrayList<Integer>(); leftToRight.add(pRoot); int start=0,end=leftToRight.size(); TreeNode tmp; while(!leftToRight.isEmpty()||!rightToLeft.isEmpty()){ while(!leftToRight.isEmpty()){ tmp=leftToRight.pop(); layer.add(tmp.val); start++; if(tmp.left!=null)rightToLeft.push(tmp.left); if(tmp.right!=null)rightToLeft.push(tmp.right); if(start==end){ start=0; end=rightToLeft.size(); result.add(layer); layer=new ArrayList<Integer>(); } } while(!rightToLeft.isEmpty()){ tmp=rightToLeft.pop(); layer.add(tmp.val); start++; if(tmp.right!=null)leftToRight.add(tmp.right); if(tmp.left!=null)leftToRight.add(tmp.left); if(start==end){ start=0; end=leftToRight.size(); result.add(layer); layer=new ArrayList<Integer>(); } } } return result; }

上面的代码可以更简化