剑指 offer之从上向下打印二叉树_java

题目：从上向下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

解题思路：

广搜的套路就是用一个队列保存将要搜索的这一层的元素，然后逐个搜索；

1、将第一个元素加入队列

2、队列不为空时取队首元素

3、将下一层元素加入队尾

4、调到第二步，直到队列为空

代码实现：

import java.util.ArrayList;
import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
	public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
		//存储结果
		ArrayList<Integer> list=new ArrayList<>();
		if(root==null) {
			return list;
		}
		//借助队列来实现
		Deque<TreeNode> deq=new LinkedList<TreeNode>();
		//添加根节点
		deq.add(root);
		//循环取出节点
		while(!deq.isEmpty()) {
			TreeNode node=deq.poll();
			list.add(node.val);
			if(node.left!=null) {
				//添加左子树
				deq.add(node.left);
			}
			if(node.right!=null) {
				//添加右子树
				deq.add(node.right);
			}
		}
		return list;
    }
}