algorithm - 有多少二叉树可能满足给定的前序和后序遍历？

Question

例如

预购->0,1,2

后序->2,1,0

      0
     /
    1
   /
  2

      0
     /
    1
     \
      2

      0
       \
        1
       /   
      2

      0
       \
        1
         \
          2

对于上述情况，这些是可能的 4 棵二叉树。对于任何前序和后序遍历，一般可能有多少棵树？

Answer 1

您的问题有两个答案:

• 对于二叉树的给定后序和前序遍历，您只能找到一棵树。 (注意对二进制的强调!我只允许根的度数为 2)
  this answer 中给出了证明草图，您还可以在其中找到重建算法。

• 如果你的树允许有度数为 2 的内部节点，即只有一个 child 的节点，那么你可以将它放在左边或右边，相应的子树在前和中的位置后序遍历不会改变。所以如果你有 k 个这样的节点，你就有 2^k 个等效树