algorithm - 不能从给定的 Inorder/Preorder/Postorder 遍历构造树

Question

我知道如果没有中序和先序/后序遍历就无法构建树。因为对于给定的(仅 Inorder/Preorder/postorder)，可能会生成更多数量的树。是否有任何算法或机制可以根据给定的(仅中序/先序/后序遍历)计算唯一树的数量。

Eg : a b c d e f g this is my Inorder traversal. 

使用给定的中序遍历可以构造多少棵独特的树。

我试过他们是谷歌，但没有一个解释清楚

任何帮助将不胜感激...

Answer 1

算法如下:

让 P(N) 表示具有 N 个节点的可能的树数。让节点的索引为 1,2,3,...

现在，让我们选择树的根。任何给定的 N 节点都可以是根。假设节点 i 已被选为根节点。那么，中序序列中i左边的所有元素都必须在左子树中。同样，向右。

所以，总的可能性是:P(i-1)*P(N-i)

在上面的表达式中，i 从 1 到 N 变化。

因此我们有，

P(N) = P(0)*P(N-1) + P(1)*P(N-2) + P(2)*P(N-3)....

基本情况将是:

P(0) = 1 
P(1) = 1

因此这可以通过使用动态编程来解决。