24.二叉树的层序遍历

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public List> levelOrder(TreeNode root) {
18         // 判断特殊情况，即空树；
19         if(root == null) return new ArrayList();
20         // 创建二维列表，里面装的元素是一维列表；
21         // 这里的多态只针对最外层的ArrayList，而对内层的List在这里并没有使用多态,而是在32行中定义的时候使用多态；
22         List> ret = new ArrayList>();
23         // 创建队列，将每一行中的元素按从左至右的顺序放入该层的队列中；
24         Queue queue = new LinkedList();
25         //queue.offer()函数：添加一个元素并返回true;如果队列已满，则返回false
26         queue.offer(root);
27 
28         while(!queue.isEmpty()) {
29             // 记录该层queue的大小
30             int currentLevelSize = queue.size();
31             // 用一个一维列表记录存入
32             List level = new ArrayList();
33             // 遍历该层queue，将队列中的元素依次读入level中，并将他们的左右子树放进队列中(为下一轮队列的循环做准备);
34             for (int i = 0;i < currentLevelSize;i++) {
35                 // 获取queue中的节点,queue.poll()函数：移除并返问队列头部的元素;如果队列为空，则返回null
36                 TreeNode node = queue.poll();
37                 // 将节点值加入level中;
38                 level.add(node.val);
39                 //将该节点的左右子树节点放入队列中;
40                 if (node.left != null) queue.offer(node.left);
41                 if (node.right != null) queue.offer(node.right);
42             }
43             // 将该层的所有节点值放入ret中;
44             ret.add(level);
45         }
46         return ret;
47     }
48 }