把二叉树打印成多行-剑指Offer

把二叉树打印成多行

题目描述

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

思路

1. 都是从左往右打印，我们可以使用队列
2. 若要一行一行区别开来打印，我们可以用两个队列
3. 也可以用一个队列，然后用两个标志位来标注哪些是属于一行里的结点，一个指针指向下一行的最后一个进队列的（point），一个指针指向上一行最后一个进入队列的（end），当出队列到end时，打印上一行，然后把end指针下移到下一行point处，继续循环打印

代码

import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (pRoot == null) { return result; } TreeNode point = null; TreeNode end = null; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(pRoot); point = pRoot; end = pRoot; ArrayList<Integer> list = new ArrayList<Integer>(); while (!queue.isEmpty()) { TreeNode node = queue.poll(); // 出队列，然后分别将左右节点入队列 if (node.left != null) { queue.offer(node.left); point = node.left; // 更新当前这行最后一个进入队列的 } if (node.right != null) { queue.offer(node.right); point = node.right; } list.add(node.val); if (node == end) { result.add(list); list = new ArrayList<Integer>(); end = point; // 移到下一行中 } } return result; } }