Binary Tree Level-Order Traversal

LeetCode 102 二叉树层序遍历：两种写法（带 level 映射 vs 按层处理）。

#resource / algorithm #type / howto #status / evergreen #ds / tree #algo / bfs #source / leetcode

[!info] related notes 算法面试题型 MOC 二叉树高频题

Binary Tree Level-Order Traversal

LeetCode: https://leetcode.cn/problems/binary-tree-level-order-traversal/

推荐写法：按层处理（levelSize）

每一轮先取当前队列长度 size，这一轮只弹出 size 个节点，天然形成一层。

import java.util.*;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                level.add(cur.val);
                if (cur.left != null) q.add(cur.left);
                if (cur.right != null) q.add(cur.right);
            }
            ans.add(level);
        }
        return ans;
    }
}

备选写法：记录 level（不太推荐）

用 map 记录节点层数，写起来更绕，也更费常数。

import java.util.*;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;

        Queue<TreeNode> q = new LinkedList<>();
        Map<TreeNode, Integer> levelMap = new HashMap<>();
        q.add(root);
        levelMap.put(root, 0);

        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            int level = levelMap.get(cur);
            if (ans.size() == level) ans.add(new ArrayList<>());
            ans.get(level).add(cur.val);

            if (cur.left != null) {
                q.add(cur.left);
                levelMap.put(cur.left, level + 1);
            }
            if (cur.right != null) {
                q.add(cur.right);
                levelMap.put(cur.right, level + 1);
            }
        }
        return ans;
    }
}

二叉树高频题