我在解决一个算法 问题:
给定一个二叉树
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
)。
[2, 4, 3, 1]
作为一个删除序列,不确定如何更好地称呼它。 - Quimby