二叉树的层序遍历

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

示例 1：

img

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

示例 2：

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

示例 3：

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

提示：

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

层序遍历需要借助队列

队列不为空时执行：

  1. 将根节点入队
  2. 获取队列长度size
  3. 如下行为重复size遍：
    • 出队
    • 如果有左孩子，左孩子入队
    • 如果有右孩子，右孩子入队

size就是每一层的节点数，每次处理一层的节点

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
40
41
42
43
44
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int max = 2000;
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        TreeNode[] queue = new TreeNode[max];
        int l = 0;
        int r = 0;
        if(root==null){
            return res;
        }
        queue[r++] = root;
        while(l<r){
            int size = r-l;
            List<Integer> list = new ArrayList<>();
            for(int i = 0;i<size;i++){
                TreeNode cur = queue[l++];
                list.add(cur.val);
                if(cur.left!=null){
                    queue[r++] = cur.left;
                } 
                if(cur.right!=null){
                    queue[r++] = cur.right;
                }
            }
            res.add(list);
        }
        return res;
    }
}