如果只能删除叶子，则删除二叉树的方法数
Number of ways to delete a binary tree if only leaves can be deleted
我正在解决一个算法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，但我无法制定递归关系。
如果你能提供一些hints/guidance，我将不胜感激。谢谢！
编辑：
给定以下树：
1
/ \
2 3
/ \
4 5
我们可以通过两种方式删除 3 的子项（4、5）；但是如何使用这个信息来确定根节点1的路数呢？ （预期答案是 8）。
对于给定节点 X，我们想知道 u(X) - 唯一删除序列的数量。
假设此节点有两个 children 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| choose |A|] * u(A) * u(B)。
如果我们定义 u(empty)=1.
它也适用于空 children
小心溢出，组合的数量会很快爆炸。
我正在解决一个算法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，但我无法制定递归关系。
如果你能提供一些hints/guidance，我将不胜感激。谢谢！
编辑： 给定以下树：
1
/ \
2 3
/ \
4 5
我们可以通过两种方式删除 3 的子项（4、5）；但是如何使用这个信息来确定根节点1的路数呢？ （预期答案是 8）。
对于给定节点 X，我们想知道 u(X) - 唯一删除序列的数量。
假设此节点有两个 children 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| choose |A|] * u(A) * u(B)。
如果我们定义 u(empty)=1.
小心溢出，组合的数量会很快爆炸。