从上往下打印二叉树
第二十一题:从上往下打印二叉树
题目描述
从上往下打印出二叉树的每个节点,同层节点从左至右打印。
思路:
BFS 宽度优先遍历
注意:
①代码的鲁棒性(极限条件的考虑)
②借助一个队列Queue
③Basecase 队列不为空
④左右孩子依次压入
具体实现如下图所示:
具体实现代码如下:
//树的定义
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
/**
* 从上往下打印二叉树
*/
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
//存储结果
ArrayList<Integer> list = new ArrayList<>();
//代码的鲁棒性
if (root == null){
return list;
}
//定义队列
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
//存储变量
TreeNode cur;
while (!queue.isEmpty()){
//弹出队列头部结点
cur = queue.poll();
list.add(cur.val);
//依次压入左右孩子
if (cur.left != null){
queue.add(cur.left);
}
if (cur.right != null){
queue.add(cur.right);
}
}
return list;
}