题目重点：DoorDash Phone Coding 可读原题：节点 value 变动算 1，整棵新增/删除分支按节点数计，按兄弟 key 对齐递归比较。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 示例把同一父节点下的 child key 视为唯一，同 key 表示同一逻辑菜单项；兄弟顺序变化不计变化。题目未披露重复 key 或移动节点的规则。
- 若根 key 不同，视为旧树整棵删除与新树整棵新增，计数为两边节点总数；这是显式训练契约。
- value 以字符串完全相等判断；若真实题目有大小写、空值或对象字段比较规则，需按题面替换。
解题路线
- 递归比较同位置逻辑节点：一边为空则返回另一边整棵子树节点数；两边 key 不同按删除+新增处理。
- key 相同则先比较 value 是否不同，再把两边 children 按 key 建索引，对 key 并集逐个递归。
- 新增/删除子树不再逐个比较 value，因为每个节点已作为新增/删除计入；全树只遍历一次量级。
手动走一遍
旧树 root(A=1,B=2)，新树 root(A=9,C=3)：A 同 key 但 value 变算 1，B 删除算 1，C 新增算 1，总数 3。若 B 下有两个子节点，删除 B 整分支应算 3，而非 1。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Count changed menu nodes under explicit sibling-key matching rules."""
from dataclasses import dataclass, field
@dataclass
class MenuNode:
key: str
value: str
children: list["MenuNode"] = field(default_factory=list)
def count_changes(old: MenuNode | None, new: MenuNode | None) -> int:
def size(node: MenuNode | None) -> int:
return 0 if node is None else 1 + sum(size(child) for child in node.children)
if old is None or new is None:
return size(old) + size(new)
if old.key != new.key:
return size(old) + size(new)
before = {child.key: child for child in old.children}
after = {child.key: child for child in new.children}
if len(before) != len(old.children) or len(after) != len(new.children):
raise ValueError("sibling keys must be unique")
changed = int(old.value != new.value)
for key in before.keys() | after.keys():
changed += count_changes(before.get(key), after.get(key))
return changed
复杂度
旧/新树合计 N 个节点，哈希 children 索引与遍历预期 O(N) 时间，递归栈 O(H)；各层局部字典累计 O(N) 空间。若 key 的哈希退化，需按实际语言的 map 保证重新评估。
易错点与追问
容易失分的边界
- 按 child 数组相同下标比较会把纯重排误判为多个变化；应按 key 对齐。
- 新增/删除 branch 只计根节点会漏计后代；必须返回整棵子树节点数。
- 当某 key 同时在旧/新树出现但父节点不同，这属于移动还是删加，题目未定。示例按完整父路径识别，因此算旧路径删除加新路径新增。
- 若允许同一父节点下重复 key，字典会覆盖节点；示例直接拒绝该输入，需先明确实例 ID 才能支持重复。
继续深挖
- 若树很深，递归可改为显式栈，避免语言调用栈限制；计数逻辑不变。
- 若要输出具体 diff 而不只是数量，在递归时记录节点路径、变更类型和新旧 value；整分支可展开或压缩为子树事件。
