c++ - 如果只能删除叶子，则删除二叉树的方法数

Question

我正在解决一个算法 question :

You are given a binary tree root. In one operation you can delete one leaf node in the tree. Return the number of different ways there are to delete the whole tree. So, if the tree is:

    1
  /  \
 2     3
     /
    4

预期的答案是3:[2, 4, 3, 1],[4, 2, 3, 1] 和[4, 3, 2, 1]。

一直在苦思冥想，却不知道递归函数该如何表述。沿着Climbing Stairs的思路思考我们计算“你可以通过不同的方式爬到顶部”的问题，我想我必须使用DP，但我无法制定递归关系。

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

编辑:给定以下树:

    1
  /  \
 2     3
     /   \
    4     5

有两种方法可以删除 3 的 child (4，5)；但是如何使用这个信息来确定根节点1的路数呢？ (预期答案是 8)。

Answer 1

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

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

你可以为 X 构造多少个删除序列？您可以从 u(A) 和 u(B) 中获取任意两个序列，并将它们组合在一起。如果满足以下条件，结果将是 X 的有效删除序列:

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

This means you want to find out the number of ways you can interleave both sequences (并附加 X)。

请注意，删除序列的长度是树的大小，如果您考虑一下，这有点微不足道。

还请注意这样一个事实，即我们可以通过这种方式为 X 生成所有删除序列，这可能不是那么简单。

所以如果我没记错的话，你要找的公式是 u(X)= [|A|+|B|选择 |A|] * u(A) * u(B)。

如果我们定义 u(empty)=1，它也适用于空 child 。

请注意溢出，组合的数量会很快爆炸。