面试题：如何生成可双向还原的二叉树Diff？实现createDiff函数

问题回顾 #

给定两棵二叉树，说明如何生成一个Diff，使得拥有该Diff和其中任意一棵二叉树时，都能生成另一棵二叉树。需实现函数createDiff(Node tree1, Node tree2)以返回该Diff。

示例树结构 #

树1

4
   /   \
  3     2
 / \   / \
5  8 10 22

树2

1
   \
    4
   /  \
  11  12

原方案的局限性 #

你提到的「转数组+逐元素求差」思路，逻辑上是直观的，但确实存在两个硬伤：

• 值冲突风险：如果树中本身存在值为-1的节点，会和你定义的空节点标记混淆，导致Diff解析时完全出错
• 空间冗余问题：对于稀疏二叉树（比如示例里的树2），数组会塞满大量-1占位符，Diff的体积会非常臃肿，完全没必要

更优的结构化Diff思路 #

我们可以设计一个和二叉树同构的递归Diff结构，用明确的操作类型替代模糊的数值标记，既解决值冲突，又节省空间。

核心思路：分层递归记录操作 #

遍历两棵树的对应节点，针对每对节点的关系，记录以下四种操作类型之一：

1. UPDATE：两个节点都存在，但值不同 → 记录新旧值的映射（比如(old_val, new_val)，支持双向转换）
2. ADD：tree1有节点，tree2对应位置为空 → 记录tree1的节点完整结构（用于从tree2生成tree1）；反之则记录tree2的节点结构（反向生成用）
3. DELETE：tree1对应位置为空，tree2有节点 → 标记删除操作；反之同理
4. REPLACE：当两个节点的子树结构差异极大时（可选优化），直接标记替换整个子树，避免递归生成大量细粒度Diff

伪代码定义Diff节点 #

class DiffNode:
    def __init__(self, op, content=None, left=None, right=None):
        self.op = op  # 取值：UPDATE/ADD/DELETE/REPLACE
        self.content = content  # UPDATE存(old,new)；ADD/REPLACE存节点结构；DELETE无需额外内容
        self.left = left  # 左子树的DiffNode
        self.right = right  # 右子树的DiffNode

示例Diff生成过程（针对树1和树2） #

1. 根节点：tree1根为4，tree2根为1 → 生成UPDATE类型的DiffNode，content=(1,4)
2. 根节点左子树：tree1有节点3（带左5、右8），tree2左子树为空 → 生成ADD类型的DiffNode，content为节点3的完整子树结构
3. 根节点右子树：tree1右子树是节点2（带左10、右22），tree2右子树是节点4（带左11、右12）→ 递归处理：
   • 节点值：2 vs 4 → UPDATE(4,2)
   • 左子节点：10 vs 11 → UPDATE(11,10)
   • 右子节点：22 vs 12 → UPDATE(12,22)

双向生成逻辑 #

• 从tree2 + Diff生成tree1：遍历tree2和Diff节点，按操作类型处理：
  • UPDATE：将当前节点值替换为content中的new_val
  • ADD：在对应位置插入content记录的节点结构
  • DELETE：删除当前节点
  • REPLACE：用content的子树替换当前子树
• 从tree1 + Diff生成tree2：反向操作即可，比如UPDATE用content中的old_val替换，ADD改为删除，DELETE改为插入

额外优化点 #

• 如果节点有唯一ID，可以先基于ID匹配节点，这样能处理节点移动的场景（比如节点从左子树移到右子树），而不只是简单的增删改
• 序列化Diff时可以用紧凑格式，比如用JSON把操作类型缩写为U/A/D/R，进一步减小体积

内容的提问来源于stack exchange，提问作者crysis