二叉树层序遍历-90%的人都用错了方法！

在这里插入图片描述

今天来聊聊二叉树的层序遍历问题。这道题在面试中的出镜率极高,是 BFS(广度优先搜索)的经典应用。

方法1:HashMap 记录层级

代码逻辑

核心是用 HashMap 记录每个节点所在的层级。

先将根节点入队并标记为第 0 层,然后逐个出队处理节点,根据 HashMap 中的层级信息将节点值放入对应层的列表中,同时将子节点入队并标记为下一层。这样通过 HashMap 作为"层级标签",让每个节点都能准确找到自己该归属的那一层。

代码实现

 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


public static List<List<Integer>> levelOrder1(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root != null) {
        Queue<TreeNode> queue = new LinkedList<>();
        HashMap<TreeNode, Integer> levels = new HashMap<>();
        
        queue.add(root);
        levels.put(root, 0); // 根节点在第0层
        
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int level = levels.get(cur);
            
            // 如果当前层还没有列表,就创建一个
            if (ans.size() == level) {
                ans.add(new ArrayList<>());
            }
            
            // 将当前节点加入对应层
            ans.get(level).add(cur.val);
            
            // 将子节点加入队列,并记录它们的层级
            if (cur.left != null) {
                queue.add(cur.left);
                levels.put(cur.left, level + 1);
            }
            if (cur.right != null) {
                queue.add(cur.right);
                levels.put(cur.right, level + 1);
            }
        }
    }
    return ans;
}

方法2:按层处理优化

代码逻辑

在每轮循环开始时,先用 size = r - l 记录当前队列中有多少个节点(即当前层的节点数),然后用 for 循环恰好处理这 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


public static int MAXN = 2001;
public static TreeNode[] queue = new TreeNode[MAXN];
public static int l, r; // l:队列头指针, r:队列尾指针

public static List<List<Integer>> levelOrder2(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root != null) {
        l = r = 0;
        queue[r++] = root;
        
        while (l < r) {
            int size = r - l; // 当前层的节点数量
            ArrayList<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;
                }
            }
            
            ans.add(list);
        }
    }
    return ans;
}