2026-11-05 AI Agent 面试训练#

题目#

你的团队维护订单服务，依赖用户服务。两个服务各自的单测和集成测试全部通过，联调环境也验证过一轮，但每次发版后仍有偶发故障：上游新增字段时下游解析崩了、枚举多了一个取值下游没处理、错误码语义变了导致下游把”无权限”当”未找到”重试。面试官问：契约测试（Contract Testing）是什么？它验证什么、不验证什么？在这个故障场景里它应该放在哪个环节？

先思考#

1. 想一想：两个服务各自”测试通过”，通过的到底是哪两份互不相干的断言？它们之间缺少的那份东西是什么？
2. 集成测试跑一次很贵，环境也难维护；如果要验证”交互约定没被破坏”，验证的最小对象是什么？
3. “谁提出约定”很重要：接口文档由提供方单方面维护，和由消费方的真实期望驱动的契约，差别在哪？
4. 契约测试通过后，还有哪些故障它是管不到的？

参考答案#

契约测试验证的是”服务之间交互约定的实现一致性”，而不是任何一方内部业务逻辑的正确性：消费方用真实调用生成契约文件（它期望的请求与响应，含结构、必填性、枚举取值、状态码），提供方在 CI 中逐条回放所有消费方的契约，任何一条不满足就挡住发版。适用边界：适合多团队维护的内部 HTTP/RPC 依赖，属于 CI 门禁层的廉价验证；它不验证端到端业务流程、不验证性能与安全，也不能覆盖未写进契约的隐式行为。示例：订单服务调用 GET /users/{id}，契约约定 200 时返回 user_id（string）与 status（enum：active / frozen）；消费方测试用 mock 跑业务逻辑并产出契约，提供方 CI 中用 verifier 回放——某天提供方把 user_id 改成 number、status 加了 deleted 枚举，契约回放立即失败，故障挡在发版前而不是联调现场。相近概念区别：schema 校验只验结构不验语义与状态组合；集成测试用真实依赖、慢且环境耦合，验证的是”拼起来能不能跑”；端到端测试验证业务流程但组合爆炸。契约测试的验证对象最小——恰好是”双方对交互的期望是否仍一致”。典型工程应用：微服务 CI 门禁，提供方上线前跑全部消费方契约，“不兼容变更直接不可合并”。

面试现场回答（1–2 分钟）：契约测试解决的是”各自都绿、拼起来崩”的问题。它把交互约定本身作为被测对象：消费方按真实期望生成契约，提供方在 CI 回放契约，双方通过同一份契约对齐，而不是各自 mock 一套想象中的对方。它轻量、可在 CI 高频运行，是集成测试和端到端测试之间的低成本防线；但它只覆盖显式写入契约的交互，不验证业务流程、性能和安全，所以它是分层测试的一环而不是替代品。本题场景中，字段类型、枚举扩展、错误码语义三类故障都应被契约捕获——前提是契约里写明了这些维度。

关键点#

1. 被测对象是”约定”本身，不是任何一方的业务逻辑；两方各自单测全绿不能推出交互一致。
2. Consumer-driven：契约由消费方的真实期望驱动，提供方单方面维护的接口文档不是契约测试。
3. 契约回放发生在提供方 CI，价值在”不兼容变更挡在合并/发版前”，而不是事后联调。
4. 边界：不覆盖端到端流程、性能、安全与未写入契约的隐式行为（如超时特征、限流行为）。
5. 契约要写语义维度（枚举、错误码含义），只写结构会漏掉本题场景里最典型的故障。

常见误区#

1. 把契约测试当集成测试替代品：它不验证真实依赖拼起来后的行为，性能、连接、环境问题仍然只能靠集成与线上观测。
2. 契约里写死具体业务数据（如具体订单号、具体金额），导致提供方正常变更也触发契约失败，团队随后干脆关闭验证。
3. 提供方自己写一份”契约”自己验证，看起来有流程，实际上消费方期望从未参与，还是单向接口文档。

延伸学习#

• Pact 官方文档（consumer-driven contract testing 的标准实现，含 provider verifier 与 broker 的工作方式）：https://docs.pact.io
• Martin Fowler《Integration Contract Tests》（经典辨析文章）：https://martinfowler.com/bliki/IntegrationContractTest.html

题目#

面试官：现代模型的上下文窗口已经到百万级，“上下文装不下”似乎不再是问题。那为什么工程实践里仍然要专门设计”上下文写入与选择策略”？它解决什么问题、和上下文压缩是什么关系？在 Agent 系统里它由谁负责——模型自己，还是你的代码？

先思考#

1. 窗口大只解决了”装得下”，模型”用得好”吗？想一想长上下文下的注意力分布问题和每 token 的成本曲线。
2. 一轮对话里可进上下文的内容有好几类：系统指令、工具定义、任务状态、工具结果、召回记忆、对话历史。它们的重要性和时效一样吗？
3. “选择”发生在内容进入上下文之前，“压缩”发生在之后——两者针对的失败形态有何不同？
4. 如果选择策略写成一句提示词（“请你自己挑重点”），会发生什么？

参考答案#

上下文写入与选择策略决定”哪些信息、以什么形式、在什么时机进入模型上下文”，它是组装期的确定性工程决策。适用边界：窗口再大也需要选择——成本随 token 线性上涨，注意力在超长上下文中分布不均（lost in the middle），工具结果原文、过期记忆和无关内容会稀释甚至污染有效信息；大窗口的承诺是”能处理”，不是”每个位置都被同等可靠地使用”。示例：客服 Agent 的上下文组装分三层——固定层（系统指令、工具定义，前缀稳定以命中提示缓存）、任务层（结构化订单状态文件，每轮重写为权威快照）、动态层（只注入与当前查询相关的 2 条知识片段和最近一次工具结果，其余工具结果只留引用与摘要），而不是全量对话历史加全部工具输出。相近概念区别：压缩是事后对已进上下文的内容做有损或无损缩减，选择是事前决定进不进；RAG 是选择策略在”外部知识”维度上的特例；提示缓存是布局问题（内容怎么排），选择是内容问题（放什么）。典型应用：Agent 系统中的 context builder 是一段确定性代码——固定层拼装、任务层状态快照、动态层按相关性预算截断，并保留”被剔除内容的引用”以便需要时二次检索。

面试现场回答（1–2 分钟）：窗口大解决了容量，不解决质量、成本和污染。写入与选择策略是在组装期由代码做的确定性决策：什么进（写入）、进多少、什么时机进（just-in-time 检索还是预注入）。它的三个直接收益是成本可控、注意力集中在高价值内容上、避免无关工具结果污染行为。它和压缩互补：选择管”事前不放进来的”，压缩管”已经进来的怎么瘦身”。关键立场是：选择是代码的职责，不能下放给模型在上下文里自己挑——那是把确定性决策变成概率性行为。

关键点#

1. 选择的三个驱动因素：token 成本、注意力分布、污染风险——窗口大小只影响第一个。
2. 选择是组装期决策，归属确定性代码；提示词里让模型”自己挑重点”不是选择策略。
3. 写入要区分内容类型：约束与状态必须在场（且是权威快照），工具结果按需注入、留引用即可。
4. 与压缩、RAG、提示缓存的分工：压缩管事后瘦身，RAG 管外部知识按需注入，缓存管前缀布局。
5. 选择策略可评测：约束性内容做 pinned 断言（必须在场），各层做消融实验验证贡献。

常见误区#

1. 把所有工具结果原文塞进上下文”反正装得下”：成本线性上涨，且无关内容降低关键指令的执行质量，还破坏提示缓存前缀稳定性。
2. 用提示词代替选择逻辑：“请从以上内容中挑出相关信息”——选择被交给概率性过程，失败形态是随机的漏选，且无法做确定性评测。
3. 只按 token 预算做”均匀截断”，不管信息依赖：截掉的恰好是约束、标识符等低成本高价值内容，留下大段无害但无用的文本。

延伸学习#

• Anthropic 工程博客《Effective context engineering for AI agents》（上下文组装、just-in-time 检索与压缩的官方工程视角）：https://www.anthropic.com/engineering/effective-context-engineering-for-ai-agents
• Liu et al.《Lost in the Middle: How Language Models Use Long Contexts》（注意力分布随位置变化的原始证据）：https://arxiv.org/abs/2307.03172

题目#

你负责一个企业内部 Agent 平台，接了 200 多个内部团队的客服、工单、代码辅助类 Agent，后端路由三类模型（旗舰 / 轻量 / Embedding）。近两个月平台月度 token 账单涨了 3.2 倍，但”日活跃任务数”只涨了 30%；同时客服类 Agent 的 P95 端到端延迟从 8 秒涨到 25 秒。财务要求按团队分摊成本，工程侧要求定位浪费在哪。现有埋点只有会话级的 token 用量汇总——只知道”哪个会话花了多少钱”，回答不了”钱花在哪个任务、哪个环节、哪类调用上”。初步排查发现三类嫌疑并存：部分团队出现重试风暴、部分 Agent 每轮注入全量历史导致上下文膨胀、部分简单任务被误路由到旗舰模型。要求：设计一套按任务、按环节归因的成本与延迟度量体系，并驱动治理；不能停服改造，埋点上线要灰度。

先思考#

1. “日活 +30%、账单 +220%“：差值就是每任务平均成本的恶化。每个任务的成本由哪几个乘法因子构成？哪个因子对重试、上下文膨胀、路由错配分别敏感？
2. 会话级汇总缺了什么？如果一次会话里有 5 个任务、每个任务 10 次模型调用、其中 2 次是重试，你需要哪些维度字段才能把每一笔 token 账拆开？
3. 缓存命中的调用和未命中的调用单价不同、批量折扣不同——归因时用”名义单价 × token 数”会算出什么错误结论？
4. 埋点放在哪里最能保证覆盖完整：各业务 SDK 里、还是模型网关统一入口？

参考答案#

先给结论：账单 3.2 倍不是使用量增长，而是三类浪费叠加——重试放大、上下文膨胀、路由错配；现有的会话级汇总无法区分它们，因为归因要求每次模型调用都携带任务与环节维度，而会话恰恰是这两个维度的并集。核心方案：在模型网关统一打点，每次 LLM 调用记录一组归因字段（trace_id、task_id、tenant、step_name、model、prompt_tokens、completion_tokens、cache_read_tokens、cache_write_tokens、latency、retry_count、终止原因、当时路由版本），任务级聚合通过 trace 树回溯得到”任务 → 环节 → 调用”三层透视；延迟同理按 step 记录排队时间与 TTFT / 生成时间。执行流程：网关响应流旁路异步打点 → 按租户分区的时序/列式存储 → 离线聚合出”团队 × 任务类型 × 环节”的成本透视与”环节 × 分位数”的延迟透视 → 与账单对账。技术选型：网关打点优于 SDK 埋点（覆盖所有业务方、与框架无关、字段统一），日志事后解析只作兜底；代价是网关成为关键路径组件，需要自身的高可用与降级（打点失败只降级观测、不阻断调用）。方案取舍：维度越全基数越大——按上题 S02（2026-10-29）同样的标签预算原则，task_id 放事件属性而非指标标签，聚合在离线层完成；实时预算熔断（任务超过 token 预算即拒绝）与离线账单分工，避免在线分摊的计算开销。失败路径与边界：重试调用必须带 retry=true 与同一 step_name，避免重试被记成新环节导致双计；缓存命中按实际计费价折算，透视表同时给名义成本与折后成本两列；打点丢失用请求数与账单请求数做对账，覆盖率低于阈值告警；任务失败的成本仍记入该任务（失败也是成本，治理动作针对失败原因）；时钟用网关统一时钟，避免端侧时钟偏差扭曲延迟分位。安全与权限：账单与明细按租户隔离，团队只能看自己的归因；成本数据不属于模型输出，不进上下文。验证指标：内部核算与云厂商账单误差 < 2%；归因覆盖率（携带完整维度字段的调用占比）从当前约 40% 提到 > 99%；分摊争议率（团队申诉）作为分摊质量的业务指标。三层能力归属：模型能力决定单价与延迟曲线；编排能力决定调用次数、上下文形状与缓存命中——三类浪费全部落在这里；计量、分摊、熔断是传统软件的确定性职责，不得交给模型。

追问 1：缓存命中怎么归因？ 每条调用同时记 cache_read / cache_write 与名义 token 数，成本按计费规则折算后归因；治理指标要分开看”命中率下降”与”单价上涨”，否则缓存策略调优会被单价波动掩盖。 追问 2：失败任务的成本算谁的？ 记入发起任务及其环节，并在透视表中单列”浪费成本”（重试、超限熔断、路由撤销）——治理的目标是让浪费列收缩，而不是把失败成本藏进均价。 追问 3：预算熔断会不会误伤关键任务？ 分级：按任务类型设软预算（超限降级到轻量模型）与硬预算（超限拒绝并走人工通道）；熔断判定只依赖网关侧确定计数，不依赖模型自评，且熔断动作本身要打点，防止熔断层成为新的静默失败源。

关键点#

1. 归因最小维度集：task_id × tenant × step × model × cache 状态 × retry 标记——缺任何一项，三类浪费中至少一类不可判别。
2. 会话是归因的并集单位：一个会话多任务、一个任务多调用、调用间有重试与缓存差价，会话级汇总会把这些乘法全部糊在一起。
3. 成本透视必须区分名义成本与折后成本（缓存、批量折扣），否则治理动作的效果评估会失真。
4. 打点位置选在模型网关：覆盖完整、字段统一、与框架无关；打点自身故障只降级观测不阻断业务。
5. 归因的终点是治理动作：重试预算、上下文裁剪、路由策略——只出报表不出动作的归因体系维持不下去。

常见误区#

1. 用”日活任务数”或”会话数”做分母摊成本：乘法因子（重试倍率、上下文长度、路由分布）全部被均值吞掉，看起来”每任务变贵了”但不知道贵在哪。
2. 把缓存折扣后的均价当成标准单价做预算与回滚判定：命中率一变，预算曲线整体漂移，误报浪费或漏报浪费。
3. 归因只做到会话级就开工治理：对重试风暴的治理（重试预算）和对上下文膨胀的治理（组装策略）是两个不同环节的改造，归因粒度不到 step 就会治理错对象。

小型实践#

用 Python 写一个 mock 模型网关：对每次调用随机生成 task_id / step / model / cache 状态 / retry 标记并打点为 JSON Lines，随后写一个聚合脚本输出”任务 × 环节 × 模型”的成本透视表，并验证：把一条调用标记为重试后，浪费成本列正确增加而名义总成本不变。约 30–45 分钟。

延伸学习#

• OpenTelemetry GenAI 语义约定仓库（gen_ai.* 属性与 span 结构，含 token 用量与模型字段的标准化方向；状态仍为 Development）：https://github.com/open-telemetry/semantic-conventions-genai
• Anthropic / OpenAI 官方定价页中的缓存定价说明（缓存读与缓存写的计费差异，是折后成本核算的依据；具体数值随厂商与时间变化，使用前需按当日定价核验）：https://docs.anthropic.com/en/docs/build-with-claude/prompt-caching

题目#

一个 Go 编写的内部网关服务，最近三周内存水位持续上涨：RSS 每周爬升约 15%，流量低峰也不回落，最终节点 OOMKilled，重启后一切恢复正常，一两周后复发。值班同学跑了 pprof heap profile，对比三周前发现 top 函数没有明显变化，堆里也没有大对象——“堆是干净的”。同时注意到 runtime.NumGoroutine() 从稳态约 2 千涨到了 8 万；下游三周前上线了一个新接口，平均响应 800ms、P99 达 40 秒。定位根因，给出修复方案与防回归措施。

先思考#

1. 堆剖析”干净”与 goroutine 数量暴涨 40 倍，两件事如何同时成立？goroutine 的内存都存在哪里？
2. 新接口 P99 40 秒——每个调用 800ms 平均值掩盖了什么分布？调用它的代码路径在超时与取消上缺了什么？
3. 如果调用方提前 return 或 ctx 已取消，那个还在等响应的 goroutine 处于什么状态？它会自己结束吗？
4. OOMKilled 自动重启让服务”看起来自愈了”，这个兜底在什么条件下会失效？

参考答案#

先给结论：直接原因是 goroutine 泄漏——调用新接口的代码路径在部分分支提前 return（如上游连接断开、ctx 超时），没有传播取消、没有关闭响应体，导致每个异常路径都留下一个阻塞在”等响应/写 channel”上的 goroutine；堆剖析干净是因为泄漏的 goroutine 栈很小、持有的对象未成为堆 top，内存在栈内存、响应体缓冲和未释放的连接里累积，恰好不在 heap profile 的视野中心。问题拆解：①泄漏类型判定——goroutine 泄漏常与 fd 泄漏、连接泄漏相伴，NumGoroutine 趋势 + fd 数量趋势是三条最便宜的先导指标；②定位手段——/debug/pprof/goroutine 全量 dump 按创建栈聚合，8 万个 goroutine 会聚成少数几组相同栈，直接指出泄漏点；对”谁没被回收”可用 goleak 在测试中断言；③核心方案——修复生命周期所有权：谁创建 goroutine 谁负责其退出，所有下游调用带 ctx 且 ctx 从入口全链路传播，http.Client 设置整体超时与 resp.Body 必须读完或关闭，向 channel 发送前检查 ctx；④执行流程——修复 → 用真实慢接口构造异常路径回归 → 压测验证 goroutine 数稳态回归。技术选型与备选：临时止血可用滚动重启与降低并发水位，但重启不修泄漏率，流量涨时泄漏速度快于重启节奏；备选的”给每个调用包一层带超时的 wrapper”若无 ctx 传播则无效——goroutine 依然阻塞在底层 IO 上，超时只是让调用方不再等它。失败路径与边界：自动重启兜底在泄漏率超过重启速度、或泄漏同时拖垮依赖（fd 耗尽影响同节点其他服务）时失效；P99 40 秒的下游接口本身要按 SLO 治理，否则任何客户端修复只能缓解。超时与重试：客户端超时应小于下游 P99 加余量，超时后的重试必须配预算与抖动（见 2026-10-13 B01），否则重试进一步放大 goroutine 水位。性能与可用性：ctx 传播与提前取消会释放服务端资源，长尾修复后 P95 反而下降；defer resp.Body.Close() 与有限缓冲读取的成本可忽略。验证指标：稳态 goroutine 数、fd 数、RSS 在低峰回落、/debug/pprof/goroutine 中各栈组数量恒定；CI 中对调用路径跑 goleak 断言，防回归。

追问 1：为什么 heap profile 看不到泄漏？ heap profile 记录的是堆对象的分配者视角；阻塞中的 goroutine 内存主要在栈上，且它引用的缓冲可能量级不足以进入 top，所以要用 goroutine profile 而不是 heap profile 判定此类泄漏。 追问 2：该不该长期保留”OOM 后自动重启”这个兜底？ 该保留但要降级为最后防线：K8s 层的 liveness + 重启掩盖不了 fd 耗尽对同节点的影响，且重启会丢在途请求；正确的分层是先修所有权、再用水位告警在泄漏初期介入、重启只兜未知泄漏。 追问 3：无界缓存也算泄漏吗？ 算同类问题——生命周期与容量治理缺失：全局 map 只写不删，键随流量无限增长。治理同构：给缓存设淘汰（LRU/带 TTL），把”驻留内存”归属到明确策略，而不是依赖进程重启清零。

关键点#

1. 三条先导指标：goroutine 数、fd 数、RSS 低峰是否回落——三者趋势背离时优先怀疑生命周期问题而非内存大户。
2. goroutine 泄漏要查 goroutine profile（按创建栈聚合），heap profile 对栈内存不敏感；两个工具回答不同的问题。
3. 根因几乎总是”生命周期所有权缺失”：提前 return 的分支没有传播取消、没有关闭资源；修复对象是所有权结构，不是调参。
4. 客户端超时不等于取消：没有 ctx 传播，超时只让调用方离开，泄漏的 goroutine 继续阻塞。
5. 自动重启是兜底不是治理：泄漏率与重启速度的竞赛没有赢家，必须以稳态回归指标闭环。

常见误区#

1. “堆剖析正常，所以没有内存问题”——把 heap profile 当成内存问题的全集，漏掉栈、fd、连接缓冲三类不进 top 的消耗。
2. 把 OOMKilled 自动重启当解决方案：它掩盖故障、丢在途请求、且不改变泄漏率，流量增长后重启窗口被追平。
3. 只给调用加超时不传播 ctx：下游调用依然占住 goroutine 与连接，超时只是缩短了调用方的等待，泄漏照旧。

小型实践#

写一个故意泄漏的 Go HTTP handler：30% 概率走”提前 return 但不关闭 resp.Body、不传 ctx”的分支，压测 1 分钟观察 NumGoroutine 上涨；然后用 /debug/pprof/goroutine?debug=1 定位聚合栈，修复为 ctx 传播 + 读完并关闭响应体，再压测验证稳态回归。约 40–60 分钟。

延伸学习#

• Go 官方 pprof 文档（各 profile 类型的分工，含 goroutine profile）：https://pkg.go.dev/net/http/pprof
• uber-go/goleak（测试期 goroutine 泄漏断言的官方推荐实践）：https://github.com/uber-go/goleak

题目#

LeetCode 102 · Binary Tree Level Order Traversal · 二叉树的层序遍历 · Medium（难度按标准分类记录为 medium；英文官方页正文与社区讨论均按 medium 处理，本次抓取的页面未直接渲染难度标签，标注”未直接核验”）

官方链接（已核验英文页题面、约束与示例；中文站链接本次访问被安全检测拦截，未完成正文核验）：

• 英文：https://leetcode.com/problems/binary-tree-level-order-traversal/
• 中文（链接给出，本次未核验正文）：https://leetcode.cn/problems/binary-tree-level-order-traversal/

题目描述：给定二叉树的根节点 root，返回其节点值的层序遍历结果——即逐层地、从左到右访问所有节点，返回按层分组的二维数组。

输入输出：输入一棵二叉树的根节点；输出 List[List[int]]，每个内层数组是同一层的节点值，按从左到右排列。

约束：

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

示例：

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

4
输入: root = [1]
5
输出: [[1]]
6

7
输入: root = []
8
输出: []

先思考#

1. 层序遍历就是广度优先搜索（BFS），但 BFS 天然给出的只是一个访问序列——“按层分组”多出来的信息是什么？
2. 队列里某一时刻恰好包含完整的一层节点。这个时刻的队列长度，能不能作为本层的规模快照？
3. 取完快照后循环处理这一层的每个节点，把它们的子节点追加到队尾——下一轮的队列里恰好又是完整的一层。这个不变式如何保持？
4. 空树、单节点、全部左偏的链状树，输出分别应该是什么形状？

参考答案#

推荐解法：BFS + 逐层快照。维护一个队列，初始为根节点（非空时）；每轮循环先记录当前队列长度 size（这就是当前层的节点数），然后恰好出队 size 个节点收集其值，并把它们的子节点入队；每轮产出一个内层数组。正确性：不变式是”每轮循环开始时，队列恰好包含从左到右的完整一层节点”。初始时队列只有根，成立；处理第 k 层时，出队的恰是第 k 层全部节点，入队的恰是第 k+1 层全部节点且顺序为左到右，归纳成立。size 必须在循环前取快照——若用 len(queue) 动态判断，本轮入队的子节点会污染本轮计数。时间复杂度 O(n)：每个节点恰好入队、出队各一次；空间复杂度 O(n)：队列最宽为最底层节点数，最坏约 n/2（满二叉树叶层），输出不计入时为 O(n)。

1
from collections import deque
2
from typing import Optional, List
3

4

5
class TreeNode:
6
    def __init__(self, val: int = 0, left: "Optional[TreeNode]" = None, right: "Optional[TreeNode]" = None):
7
        self.val = val
8
        self.left = left
9
        self.right = right
10

11

12
class Solution:
13
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
14
        if not root:
15
            return []
16
        result = []
17
        queue = deque([root])
18
        while queue:
19
            size = len(queue)          # 本层快照：循环前固定
20
            level = []
21
            for _ in range(size):      # 恰好处理 size 个
22
                node = queue.popleft()
23
                level.append(node.val)
24
                if node.left:
25
                    queue.append(node.left)
26
                if node.right:
27
                    queue.append(node.right)
28
            result.append(level)
29
        return result

边界情况：空树返回 []（注意是空列表而不是 [[]]）；单节点返回 [[1]]；链状树每层只有 1 个节点，返回 n 层；值可为负（-1000）不影响逻辑，但构造测试时别只用正数。

测试用例（3 个 + 补充）：

1
from collections import deque
2
from typing import Optional, List
3

4

5
class TreeNode:
6
    def __init__(self, val: int = 0, left: "Optional[TreeNode]" = None, right: "Optional[TreeNode]" = None):
7
        self.val = val
8
        self.left = left
9
        self.right = right
10

11

12
def case(name, root, expected):
13
    got = Solution().levelOrder(root)
14
    assert got == expected, f"{name}: got {got}, want {expected}"
15

16

17
n = TreeNode
18
case("示例1", n(3, n(9), n(20, n(15), n(7))), [[3], [9, 20], [15, 7]])
19
case("空树", None, [])
20
case("单节点", n(1), [[1]])
21
case("左偏链", n(1, n(2, n(3))), [[1], [2], [3]])
22
case("含负值", n(-1, n(-2), n(0)), [[-1], [-2, 0]])
23
print("all passed")

面试官追问（变体）：①锯齿形层序遍历（LeetCode 103）——同一解法上按层号奇偶反转内层数组即可，也可以双向队列但没必要；②自底向上（107）——结果最后整体反转；③右视图（199）——每层快照的最后一个元素。扩展追问：“能否不用额外队列、O(1) 额外空间？“——按层分组输出依赖层边界信息，DFS 按深度索引填桶可以达到 O(h) 递归栈空间且无需队列，但迭代式 BFS 的 O(宽度) 是标准解；Morris 遍历做不到按层分组输出。可迁移能力：“取快照再处理”的分层 BFS 模式——队列当前长度即本层规模，这个模式同样适用于图的最短路层数、多源 BFS（腐烂橘子类）、以及子 Agent 任务按依赖深度分批展开的场景（广度优先逐层调度时，快照决定本批并发度）。

关键点#

1. 不变式：每轮循环开始时队列恰好是完整一层，从左到右有序。
2. size = len(queue) 必须在处理前取快照，本轮入队的子节点不得污染本层计数。
3. 空树输出 [] 而非 [[]]：先判空再进循环。
4. 复杂度：每节点进出队各一次，时间 O(n)；空间由最宽层决定，最坏 O(n)。
5. 分层快照模式可迁移到多源 BFS 与按深度分批的调度问题。

常见误区#

1. 用 while queue 直接循环、在循环体内动态读 len(queue)，导致子节点混入当前层，输出分层错误。
2. 忘记处理空树，或对空树返回 [[]]。
3. 试图用栈实现”层序”——DFS 前序得到的是路径序，不是层序；层序的本质是队列的 FIFO。

延伸学习#

• LeetCode 102 官方题目页（已核验）：https://leetcode.com/problems/binary-tree-level-order-traversal/
• 同族变体练习：LeetCode 103 锯齿形层序遍历、107 自底向上层序、199 二叉树的右视图（沿用同一分层快照模式）