只能删除叶子节点的情况下，删除二叉树的方法数

Question

我在解决一个算法 问题:

给定一个二叉树 root。你可以在一次操作中删除树中的一个叶节点。返回删除整个树的不同方式的数量。例如，如果树是：

    1
  /  \
 2     3
     /
    4

期望答案是3: [2, 4, 3, 1]，[4, 2, 3, 1]和[4, 3, 2, 1]。

我一直在思考，但不知道如何构建递归函数。按照爬楼梯问题中“到达顶部有多少不同的方法”来思考，我认为必须使用DP，但我无法构建递归关系。

如果您能提供一些提示/指导，我将不胜感激。谢谢！

编辑： 给定以下树：

    1
  /  \
 2     3
     /   \
    4     5

我们有两种方法可以删除节点3（4，5）的子节点；但是如何使用此信息确定根节点1的方式数量？（预期答案为8）。

- Someone

---

假设有一棵根节点和两个子节点的树，如果你已知每个子树被删除的方式及其大小，你能计算出整棵树被删除的方式吗？如果可以，那么你只需要知道一个叶子子树可以被删除一次，递归就变得简单了。 - Quimby

如果你已经知道了每个子树被删除的方式数量，你能计算出整棵树被删除的方式数量吗？这正是我所困扰的地方。我认为将左右子树的删除方式数量相加/相乘会有所帮助，但是一些例子表明这并不正确。我只是添加了我的分析。 - Someone

不，仅仅乘法是不够的。它还取决于每个子树的大小，或者更确切地说是删除序列的长度。然后你应该问有多少种方法可以交错删除两个删除序列和根节点。因为这构造了整棵树的删除序列。将该数字乘以两个子树都可以被删除的方式的数量。我想那应该是你的答案。 - Quimby

@Quimby，你如何定义我上面编辑的例子中的“删除序列”？我尝试使用每个子树中的“节点数量”进行计算，但没有帮助。 - Someone

我的意思是[2, 4, 3, 1]作为一个删除序列，不确定如何更好地称呼它。 - Quimby

Answer 1

对于给定节点 X，我们想知道 u(X) - 唯一删除序列的数量。

假设这个节点有两个子节点 A、B，大小为 |A|、|B|，已知 u(A) 和 u(B)。

你可以从 u(A) 和 u(B) 中任选两个序列并将它们合并起来。如果以下条件成立，则结果将是 X 的有效删除序列：

• 根节点 X 必须最后被删除。
• 不同子树中任意两个节点的删除顺序是任意的。
• 同一子树中任意两个节点的删除顺序是固定的，给定其选择的删除序列。

这意味着你需要找出交错两个序列的方法的数量（并附加 X）。

请注意，删除序列的长度是树的大小，如果你考虑一下，这有点琐碎。

此外，要想到这种方法我们可以生成所有X的删除序列，这可能不是那么琐碎。

所以，如果我数得对的话，你要找的公式是u(X)= [|A|+|B| choose |A|] * u(A) * u(B)。

如果我们定义u(empty)=1，则空子节点也适用。

只要小心溢出，组合数将会迅速增长。

- Quimby

---

请问您能否详细说明为什么在那个方程式中要选择“|A|”？ - Someone

@某人 没有任何理由，链接的答案使用了公式 m+n choose m，而组合数具有 m+n choose m 等于 m+n choose n 的性质。因此，使用 A 或 B 实际上并没有什么区别。 - Quimby