力扣102 二叉树的层序遍历 Java版本

题目描述

给你二叉树的根节点 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

思路

这个问题可以用队列解决。先把根节点入队，然后队列不空的话就出队，出队的同时遍历出队节点，如果当前节点有孩子节点就把孩子节点入队，这样遍历的顺序就是从上到下、从左到右，满足层序遍历。
在代码中详细注释了怎么一层一层地统计结果。

代码

class Solution {
    //层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        ArrayList<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        //将根节点入队
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {

            //求一下当前队列中元素的个数，这个数也就是表示这一层有多少个节点
            //因为下一层的还没有开始入队，上一层的都已经出队了，队列中的元素就都是这一层的了
            int length = queue.size();
            //因为最后要求返回的结果是分层的，所以按照层进行循环，添加到result中
            List<Integer> list = new ArrayList<>();
            while (length > 0) {
                //取出队头节点
                TreeNode node = queue.poll();
                list.add(node.val);
                //如果这个节点的左右孩子不为空，就将左右孩子入队
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                length--;
            }
            //将这一层的结果加入到result中
            result.add(list);

        }

        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39