剑指offer 60.把二叉树打印成多行

剑指offer 60.把二叉树打印成多行

题目

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

思路

和上一题类似，不过无需用两个栈了，只需要以队列来存储即可，就是简单的层次遍历，记得设置一个标记来记录每一行的长度，因为是按行输出的。

代码

public class TreeNode {

  int val = 0;
  TreeNode left = null;
  TreeNode right = null;

  public TreeNode(int val) {
    this.val = val;

  }

}

ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {

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