题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路： 这道题实质是考查树的遍历算法。从上到下打印二叉树的规律：每一次打印一个结点的时候，如果该结点有子结点， 则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直至队列中所有的结点都被打印出来为止。 广度优先遍历。
import java.util.ArrayList;
import java.util.LinkedList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private ArrayList<Integer> list =
new ArrayList<>();
public ArrayList<Integer>
PrintFromTopToBottom(TreeNode root) {
if(root ==
null) {
return new ArrayList<>();
}
LinkedList<TreeNode> linkedList =
new LinkedList<>();
linkedList.add(root);
PrintFromTopToBottom(linkedList);
return list;
}
private void PrintFromTopToBottom(LinkedList<TreeNode> linkedList) {
if(linkedList ==
null || linkedList.isEmpty()) {
return;
}
while(!linkedList.isEmpty()) {
TreeNode head = linkedList.poll();
list.add(head.val);
if(head.left !=
null) {
linkedList.add(head.left);
}
if(head.right !=
null) {
linkedList.add(head.right);
}
}
}
}
涉及知识：
广度优先遍历队列操作：LinkedList
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
package java.util;
public interface Queue<E> extends Collection<E> {
boolean add(E e);
/**
* Inserts the specified element into
this queue
if it
is possible to
do
* so immediately without violating capacity restrictions.
* When using a capacity-restricted queue,
this method
is generally
* preferable to {
@link
*
by throwing an exception.
*
*
@param e the element to add
*
@return {
@code true}
if the element was added to
this queue,
else
* {
@code false}
*
@throws ClassCastException
if the
class of the specified element
* prevents it from being added to
this queue
*
@throws NullPointerException
if the specified element
is null and
*
this queue does
not permit
null elements
*
@throws IllegalArgumentException
if some property
of this element
* prevents it from being added to
this queue
*/
boolean offer(E e);
/**
* Retrieves
and removes the head
of this queue. This method differs
* from {
@link
* queue
is empty.
*
*
@return the head
of this queue
*
@throws NoSuchElementException
if this queue
is empty
*/
E remove();
/**
* Retrieves
and removes the head
of this queue,
*
or returns {
@code null}
if this queue
is empty.
*
*
@return the head
of this queue,
or {
@code null}
if this queue
is empty
*/
E poll();
/**
* Retrieves, but does
not remove, the head
of this queue. This method
* differs from {
@link
*
if this queue
is empty.
*
*
@return the head
of this queue
*
@throws NoSuchElementException
if this queue
is empty
*/
E element();
/**
* Retrieves, but does
not remove, the head
of this queue,
*
or returns {
@code null}
if this queue
is empty.
*
*
@return the head
of this queue,
or {
@code null}
if this queue
is empty
*/
E peek();
}
