这道题目难度一般，重要的是想到以队列作为辅助来解决。 分析：因为按层打印的顺序决定了先打印的应该为根结点。为了接下来能够打印值为 8 的结点的两个子结点，应该在遍历到该结点时把值为 6 和 10 的两个结点保存到一个容器里，此时容器中含有 6 和 10 两个结点。按照从左到右的要求，先取出值为 6 的结点。打印出值 6 之后分别把 5 和 7 两个左右子结点放入容器 ，此时容器中的结点有三个，分别是10 、 5 和 7 。接下来我们从容器中取出值为 10 的结点，注意到 10 比另外两个元素先进入，因此先将 10 取出，并再把 10 的两个结点放入，此时容器中的元素为 5 、 7 、 9 、 11。由此可以看出取元素的顺序符合先进先出原则，我们则判断需要通过队列来解决这个问题。由于这四个结点都没有子结点，因此只需要依次打印即可。打印过程如图所示：
import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Queue;/** * Created by zhangshuyou on 2015/5/22. *//** * 题目描述： * 从上往下打印出二叉树的每个节点，同层节点从左至右打印(即层序遍历) * 1.元素 8 出队，放入list，得到 6 、 10 * 2.元素 6 出队，放入list，得到 (10) 5 、7 * 3.元素 10 出队，放入list，，得到 (5) (7) (9) (11) * 4.均无子结点，直接打印 */public class Solution {//建立一个数组双端队列，是大小可变数组。线程不安全，但在速度上有一定的优势。Queue<TreeNode> queue = new ArrayDeque<TreeNode>();ArrayList<Integer> list = new ArrayList<Integer>();public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {if(root == null)return list;queue.add(root); //将结点入队while(!queue.isEmpty()){TreeNode treeNode = queue.poll(); //将元素出队并保存list.add(treeNode.val); //将元素的值取到并添加到集合中if(treeNode.left != null)queue.add(treeNode.left);if(treeNode.right != null)queue.add(treeNode.right);}return list;}}class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
自信的生命最美丽！
