[!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（不太推荐）

当需要单独查询节点层数时可以使用映射；只输出层序分组时，按层处理已经足够。下面的 HashMap 依赖题目 TreeNode 默认按对象身份区分，不能按节点值合并。

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;
    }
}

两个 Java 代码块是独立备选 Solution，TreeNode 由题目提供。两者时间 O(n)；按层法队列 O(w)，映射法额外保存 O(n) 个层数，输出均为 O(n)。w 为最大层节点数，size 必须在处理当前层之前固定，不能随入队动态增长。

Related

• 二叉树高频题