剑指offer_【59】按之字形顺序打印二叉树

1.题目描述

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

2.解题思路

用一个布尔量控制从左到右还是从右到左的顺序；如果为真则他的左右孩子按照从左到右的顺序放入list中，否则按照从右到左的顺序，当本行结束之后，再把list中的数据放入一个result中。其中用一个null值作为层次的分隔符。

3.代码

public static class Solution {
      public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
      ArrayList<ArrayList<Integer>> result = new ArrayList<>();
       if (pRoot == null) {
               return result;
           }
       ArrayList<Integer> list = new ArrayList<>();
       LinkedList<TreeNode> queue = new LinkedList<>();
       queue.addLast(null);//层分隔符
       queue.addLast(pRoot);
       boolean leftToRight = true;
       while (queue.size() != 1) {
           TreeNode node = queue.removeFirst();
           if (node == null) {//到达层分隔符
               Iterator<TreeNode> iter = null;
               if (leftToRight) {
                      iter = queue.iterator();//从前往后遍历
                   } else {
                       //从后往前遍历

                       iter = queue.descendingIterator();
                   }
               leftToRight = !leftToRight;
               while (iter.hasNext()) {
                       TreeNode temp = (TreeNode) iter.next();
                       list.add(temp.val);
                   }
               result.add(new ArrayList<Integer>(list));
               list.clear();
               queue.addLast(null);//添加层分隔符
               continue;//一定要continue
             }
           if (node.left != null) {
                   queue.addLast(node.left);
               }
           if (node.right != null) {
                   queue.addLast(node.right);
               }
           }
       return result;
   }