algorithm - 具有 N 个节点且具有相同后序和中序遍历的二叉树的数目

Question

我这几天正在研究Cataln Number。我从维基百科知道树遍历。

http://en.wikipedia.org/wiki/Tree_traversal

但是，

我混淆了 1 个问题。我们可以构造多少具有 N 个节点且具有相同后序和中序遍历的二叉树？

如有任何递归关系或其他情况，我们将不胜感激。

问候。

Answer 1

如果任何地方都没有右子树，则二叉树可以具有相同的 Postoder 和 Inorder 遍历，这意味着每个根要么有左 child ，要么是最终节点(叶子)。这意味着这棵二叉树只是一个列表，因此总共有 n! 个排列方式。