题目重点：依据 OCI bar raiser 的两棵 N 叉树比较题，明确有序孩子训练语义并递归比较形状和值。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版孩子列表有顺序，节点值是整数；两树相同要求对应位置节点值相同且子树相同。
- 两个空树相同，一空一非空不同；若孩子无序，需另外解决子树匹配，不能仅 zip。
解题路线
- 先比较空值，再比较当前节点值与孩子数量；任一不同即可返回 false。
- 对应孩子按位置递归比较，全部相同则当前子树相同。按树高归纳：叶节点直接判定，父节点由值、子树数和每个已正确比较的孩子决定。
- 当树深可能超过语言递归限制，可用显式栈保存节点对；若树可共享节点或出现环，则已不是普通树，需要 visited 集。
手动走一遍
根 1 的两个孩子 [2,3] 与另树 [2,3] 相同；若另一树孩子 [3,2]，有序语义下不同。两个空根返回 true。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Ordered N-ary tree equality."""
class Node:
def __init__(self, value: int, children: list["Node"] | None = None):
self.value = value
self.children = children or []
def identical(left: Node | None, right: Node | None) -> bool:
if left is None or right is None:
return left is right
if left.value != right.value or len(left.children) != len(right.children):
return False
return all(identical(a, b) for a, b in zip(left.children, right.children))
复杂度
两树合计 N 个节点时最坏 O(N) 时间；递归栈 O(H)，H 为最大树高，最坏退化链 O(N)。若早期节点不同可提前结束。
易错点与追问
容易失分的边界
- 只比较根值或孩子数量，不深入后代。
- 不澄清孩子顺序是否影响相等性。
- 极深树递归溢出，未考虑迭代实现。
继续深挖
- 若孩子无序，同构判断如何避免直接枚举所有排列？
- 若树节点有 ID 但值相同，比较身份还是比较结构？
