给定中序序列的不同二叉树数量计算及解法咨询

当给定固定的中序遍历序列时，不同结构的二叉树数量对应第n个卡特兰数，其中n是节点的总数。

核心逻辑：递归推导 #

假设我们有n个节点的中序遍历序列为A₁, A₂, ..., Aₙ，构造二叉树时，我们可以任选一个节点作为根：

• 如果选Aᵢ作为根，那么左子树的节点是A₁到Aᵢ₋₁（共i-1个节点），右子树的节点是Aᵢ₊₁到Aₙ（共n-i个节点）。
• 左子树的可能结构数是第i-1个卡特兰数Cᵢ₋₁，右子树是第n-i个卡特兰数Cₙ₋ᵢ。
• 以Aᵢ为根的二叉树总数就是Cᵢ₋₁ * Cₙ₋ᵢ，把所有i的情况加起来就是总的二叉树数量，这正是卡特兰数的递推公式：

  C₀ = 1
  Cₙ = Σ（从i=1到n）Cᵢ₋₁ * Cₙ₋ᵢ （n ≥ 1）
  

卡特兰数的直接计算公式 #

为了避免递归计算的繁琐，卡特兰数有更直接的组合数公式：

Cₙ = (1/(n+1)) * C(2n, n)

其中C(2n, n)是组合数，表示从2n个元素中选n个的组合数，计算方式为(2n)! / (n! * n!)。

针对你的问题计算 #

你的问题中n=5，代入公式：

1. 先算组合数C(10,5) = 10! / (5! * 5!) = 252
2. 再计算卡特兰数C₅ = 252 / 6 = 42

所以，中序遍历为P、Q、R、S、T的不同二叉树共有42种。

小例子验证 #

• n=1时，C₁=1（只有单个节点的树）
• n=2时，C₂=2（根是第一个节点，右子树是第二个；或根是第二个节点，左子树是第一个）
• n=3时，C₃=5，手动枚举就能验证确实对应5种不同结构的二叉树。

内容的提问来源于stack exchange，提问作者Divyanshu Dwivedi