Apple Binary Tree Cameras OA 题解｜叶子先不装，根节点最后如何补

2026 年 8 月的 Apple IS&T 校园招聘讨论中，有参加者提到 OA 包含 10 道 CS 选择题和两道编程题，编程题涉及完全背包与 Binary Tree Cameras。讨论属于印度校园求职语境，未给出摄像头题的完整考场题面。摄像头专项练习采用 LeetCode 968 的标准规则，下方编号只用于这道单题练习，示例自编。

第一题：用最少摄像头覆盖二叉树

题目描述

给定一棵二叉树，可以在节点上安装摄像头。每个摄像头覆盖自己、父节点和直接子节点，求覆盖所有节点所需的最少数量。覆盖不会继续传到孙子节点。自编示例是一条从根到叶长为四个节点的链 A→B→C→D。在 C 装一个摄像头可以覆盖 B、C、D，但 A 仍未覆盖，最后还需要一个，答案为 2。

解题思路

后序遍历，让孩子先返回状态。只需要三个值：0 表示当前节点还没被覆盖；1 表示当前节点装了摄像头；2 表示当前节点已覆盖，但自己没装。空节点返回 2，避免给不存在的孩子补摄像头。若任意孩子返回 0，当前节点必须装摄像头，计数加一并返回 1；否则，只要有孩子返回 1，当前节点就被覆盖，返回 2；两个孩子都为 2 时，当前节点返回 0，留给父节点处理。整棵树遍历结束后，如果根返回 0，再补一个摄像头。叶子因此先返回 0。把摄像头交给父节点，可以同时覆盖叶子、父节点及父节点的另一名孩子。父节点处理完两个子树后再做决定，已有的摄像头不会遗漏子树内部节点；最后只有根没有父节点，需要单独收尾。沿四节点链从下往上，D 返回 0，C 安装并返回 1，B 返回 2，A 返回 0。根节点补装后得到 2。时间 O(n)，递归栈 O(h)，h 为树高；链状树会达到 O(n) 栈空间。

Apple OA 练习建议

先测单节点、根加两个叶子、四节点链，再用小树枚举所有摄像头放置组合，与贪心结果对照。若使用显式栈，节点第二次出栈时才合并孩子状态，否则遍历顺序就不再是后序。测评设置按自己的邀请确认。 Hyderabad IS&T SWE 记录写的是 70 分钟 CoderPad、两道 Java 题； Cupertino Intern 记录则提到一轮行为面与两轮技术面，侧重系统设计和调试。这些岗位的流程应分别看待。

FAQ

为什么空节点返回“已覆盖”？

它没有覆盖需求。返回 2 可以让叶子保持未覆盖状态，再由父节点决定安装。

能从根开始，隔一层放摄像头吗？

不能固定按层选择。不同分支长度不同，后序状态才能反映孩子是否真的还需要覆盖。

只有根一个节点，答案是多少？

1。两个空孩子都返回 2，根返回 0，最终收尾时增加一个摄像头。

参考来源

Apple IS&T 校园招聘候选人的 OA 题目反馈（2026 年 8 月） Apple Hyderabad IS&T SWE 的 CoderPad 测评记录 Apple Cupertino SWE Intern 面试记录（2025） LeetCode 968：Binary Tree Cameras 标准题意

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

微信：Coding0201
邮箱：[email protected]
Telegram：@OAVOProxy
WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。