JZ32 从上往下打印二叉树（层次遍历）

JZ32 从上往下打印二叉树（层次遍历）

JZ32 从上往下打印二叉树

• 前言
• 问题概述
• 代码实现

前言

这个题的另一个名字是——二叉树的层次遍历。
其实这题是一个模板题，因为在二叉树相关的好多题中都会用到二叉树的层次遍历。

大家都知道，二叉树的遍历方式按图来说其实可分两大类：深度优先 和 广度优先

深度优先：就是我们常听说的 前序遍历、中序遍历、后序遍历
广度优先：就是本题题解 层次遍历

问题概述

问题链接：【JZ32 从上往下打印二叉树 】

描述
不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。

数据范围:
0<=节点总数<=1000
-1000<=节点值<=1000

示例1
输入：

{8,6,10,#,#,2,1}

返回值：

[8,6,10,2,1]

示例2
输入：

{5,4,#,3,#,2,#,1}

返回值：

[5,4,3,2,1]

代码实现

import java.util.*;

public class Solution {
    public ArrayList PrintFromTopToBottom(TreeNode root) {
        // 创建一个队列 用于存放树的节点
        Queue queue = new linkedList();
        // 创建一个list集合 存放最后返回的集合
        ArrayList resList = new ArrayList();
        // 特殊情况， 如果传来的是空树
        if(root == null) return new ArrayList();
        // 1、 将头节点放到队列中
        queue.offer(root);
        // 2、 遍历队列中节点 并插入当前节点的孩子节点
        while(!queue.isEmpty()) {
            // 2.1、 获取队列头节点 并 让该节点出队列
            TreeNode head = queue.poll();
            // 2.2、将当前节点的值 放入到list集合中
            resList.add(head.val);
            // 2.3、若存在左、右孩子 则将他们放到queue中
            if(head.left != null) queue.offer(head.left);
            if(head.right != null) queue.offer(head.right);
        }
        // 3、返回list集合
        return resList;
    }
}