题解 JAVA Deque | #按之字形顺序打印二叉树# [P1]

正常level-order traversal(因为比较好理解). 在visit的时候，用Deque去存值(因为Deque既是Queue也是Stack)。如果正向就当Queue(i.e. offer), 反向就当stack(i.e. push)。最后用Collection的copy constructor把Deque转化成ArrayList。

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
      ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
      if (pRoot == null) return ret;
      
      Queue<TreeNode> q = new LinkedList<>();
      boolean odd = true;
      q.offer(pRoot);
      while (!q.isEmpty()) {
        int lSize = q.size();
        Deque<Integer> levelDeq = new ArrayDeque<>();
        while (lSize > 0) { 
          TreeNode n = q.poll();
          if (odd) levelDeq.offer(n.val);
          else levelDeq.push(n.val);  // offerFirst
        
          if (n.left != null) q.offer(n.left);
          if (n.right != null) q.offer(n.right);
          lSize--;
        }
        odd = !odd;
        ret.add(new ArrayList<>(levelDeq));
      }
      return ret;
    }
}