二叉树的计数：直接方法与间接方法

摘要: 通过二叉树计数的基础问题，了解生成函数计数的直接方法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在对与二叉树相关的算法进行算法分析时，一个非常基本的问题是：给定一些条件，问满足这些条件的二叉树共有多少种。本文我们来研究其中的一个最经典的问题：具有 N 个节点的二叉树共有多少种。

首先给出结论，记 $T_{N}$ 为具有 $N$ 个节点的二叉树的种类数。$T_{N}$ 由卡特兰数给出：

$$T_{N} = \frac{1}{N+1}\binom{2N}{N}$$

得到上述结果后，在此基础上当 $N \rightarrow\infty$ 时，$T_{N}$ 的渐近估阶在算法分析中也很关键。渐近估阶的问题本文不涉及，在以后的文章中再跟大家讨论。

本文我们聚焦于通过生成函数对 $T_{N}$ 的推导，并且以此为例，对比了使用生成函数对组合对象计数的直接方法和间接方法。

比较关键的是直接方法，直接方法的背后是用生成函数对组合结构计数的符号方法。这是一个比较完整的理论体系，涉及很多抽象的概念，这套体系最大的价值就是最终形成了将有标记或无标记的组合结构转化为生成函数的方程的一套定式化的方法。

同样地，本文不涉及这些抽象概念，重点在于看一下这种被称为符号方法的，用生成函数对组合对象计数的直接方法是怎么用的。有了这个例子，以后有时间的时候再跟大家讨论这些抽象概念，就好理解了。

导出生成函数的函数方程

二叉树是递归定义的一种结构，它或者为一个空树，或者为一个称为根的节点以及两棵子树。

如果我们把空树视为虚拟节点，相应地，非虚拟节点的节点称为内部节点。那么二叉树的递归定义还可以这样说，它或者是一个单个的虚拟节点，或者是一个连接两棵二叉树的内部节点，这两棵二叉树分别称为左子树和右子树。

通过分析和归纳可以看出，一棵 N 节点的树，就等同于一棵具有 N 个内部节点和 N + 1 个虚拟节点的树。因此问题可以转化为问具有 N + 1 个虚拟节点的树有多少棵。记其为 $T_{N}$。

间接方法

对于具有 $N+1$ 个虚拟节点的二叉树，根据其递归定义，如果左子树具有 $k$ 个虚拟节点，这样的左子树有 $T_{k-1}$，则右子树有 $N-k+1$ 个虚拟节点，这样的右子树有 $T_{N-k}$ 个，于是 $T_{N}$ 满足以下递推关系：

$$T_{N} = \sum\limits_{k=1}\limits^{N}T_{k-1}T_{N-k} \quad N > 0, T_{0} = 1$$

这是序列 $\{T_{N}\}$ 的卷积，我们可以凑以下关于生成函数的性质：

$$A(z)B(z) = \sum\limits_{n=0}\limits^{\infty}(\sum\limits_{k=0}\limits^{n}a_{k}a_{n-k})z^{n}$$

两边乘以 $z^{N}$，再对 $N$ 从 $1$ 到 $\infty$ 求和：

$$\begin{align} \sum\limits_{N=1}\limits^{\infty}T_{N}z^{N} &= \sum\limits_{N=1}\limits^{\infty}(\sum\limits_{k=1}\limits^{N}T_{k-1}T_{N-k})z^{N} \\ &= \sum\limits_{N=1}\limits^{\infty}(\sum\limits_{k=0}\limits^{N-1}T_{k}T_{N-1-k})z^{N-1}z \\ &= \sum\limits_{M=0}\limits^{\infty}(\sum\limits_{k=0}\limits^{M}T_{k}T_{M-k})z^{M}z \\ \end{align}$$

于是上式右边就凑成了生成函数的序列卷积的性质，于是上式右边即为：$zT^{2}(z)$。

另一方面，上式左边：$\sum\limits_{N=1}\limits^{\infty}T_{N}z^{N} = \sum\limits_{N=0}\limits^{\infty}T_{N}z^{N} - T_{0} = T(z) - 1$。

于是我们得到了生成函数满足的函数方程：

$$T(z) - 1 = zT^{2}(z)$$

直接方法

在间接方法中，我们首先基于组合对象的递归定义写出递归式，然后用递归式去凑生成函数的性质，最终导出生成函数满足的函数方程。

直接方法是一种更简单的方式，跳过递归式或递推关系这一步，直接确定出生成函数的函数方程。

定义 $\mathcal{T}$ 为全部二叉树的集合，记 $t \in \mathcal{T}$ 为其中一棵二叉树，$|t|$ 表示二叉树 $t$ 的虚拟节点个数。

由以上定义，可以写出 $T(z)$ 的另一种表达形式：

$$T(z) = \sum\limits_{t\in\mathcal{T}}z^{|t|}$$

其含义是：一棵恰好具有 $k$ 个虚拟节点的树对 $z^{k}$ 的系数的贡献恰好是 1。于是上式 $T(z)$ 中 $z^{k}$ 的系数就是具有 $k$ 个虚拟节点的树的个数。

由二叉树的递归定义，可以直接写出：

$$\sum\limits_{t\in\mathcal{T}}z^{|t|} = 1 + \sum\limits_{t_{L}\in\mathcal{T}}\sum\limits_{t_{R}\in\mathcal{T}}z^{|t_{L}|+|t_{R}|+1}$$

其含义是：一棵二叉树，或者没有内部节点，对应于上式的 $1$，或者它可以分为两棵独立的子二叉树，两棵子树的内部节点再加一个根节点构成原树的内部节点，对应于上式的 $\sum\limits_{t_{L}\in\mathcal{T}}\sum\limits_{t_{R}\in\mathcal{T}}z^{|t_{L}|+|t_{R}|+1}$。

另一方面，下标变量 $t_{L}$，$t_{R}$ 是独立的，也就是：

$$\sum\limits_{t_{L}\in\mathcal{T}}\sum\limits_{t_{R}\in\mathcal{T}}z^{|t_{L}|+|t_{R}|+1} = z^{1}\sum\limits_{t_{L}\in\mathcal{T}}z^{|t_{L}|}\sum\limits_{t_{R}\in\mathcal{T}}z^{|t_{R}|} = zT(z)T(z)$$

于是我们写出生成函数满足的函数方程：

$$T(z) = 1 + zT^{2}(z)$$

这种方法直接将组合结构根据其定义写成了生成函数满足的方程，而不是先写出递归式然后再去凑，因此称为生成函数计数的直接方法。它背后有一套符号体系，并且有相关的定理保证结果的正确性。但是比较抽象，以后有时间我们再展开讨论。

这是一个很好的例子，它展示了用这套抽象的符号体系来解决具体的计数问题的方法流程。以后在遇到生成函数计数的问题，可以仿照以上步骤做。

$T(N)$ 的结果

求解方程得生成函数 $T(z)$

对于函数方程 $T(z) - 1 = zT^{2}(z)$，由二次方程求根公式可得：

$$T(z) = \frac{1 \pm \sqrt{1 - 4z}}{2z}$$

考察 $z\rightarrow 0$ 的情况，上式中 $\pm$ 应该取 $-$，于是：

$$T(z) = \frac{1 - \sqrt{1 - 4z}}{2z}$$

将生成函数 $T(z)$ 展开，取 $z^{N}$ 系数

对 $(1 - 4z)^{\frac{1}{2}}$ 用广义二项式定理展开：

$$(1 - 4z)^{\frac{1}{2}} = \sum\limits_{k=0}\limits^{\infty}\binom{\frac{1}{2}}{k}(-4z)^{k}$$

于是：

$$zT(z) = \frac{1}{2}(1 - \sum\limits_{k=0}\limits^{\infty}\binom{\frac{1}{2}}{k}(-4z)^{k}) = -\frac{1}{2}\sum\limits_{k=1}\limits^{\infty}\binom{\frac{1}{2}}{k}(-4z)^{k}$$

令两边的系数相等：

$$\begin{align} T_{N} = [z^{n+1}]zT(z) &= -\frac{1}{2}\binom{\frac{1}{2}}{N+1}(-4)^{N+1} \\ &= -\frac{1}{2}\frac{\frac{1}{2}(\frac{1}{2} - 1)(\frac{1}{2} - 2)\cdot\cdot\cdot(\frac{1}{2} - N)}{(N+1)!}(-4)^{N+1} \\ &= \frac{1\cdot 3\cdot 5\cdot\cdot\cdot (2N-1)\cdot 2^{N}}{(N+1)!} \\ &= \frac{1}{N+1}\frac{1\cdot 3\cdot 5\cdot\cdot\cdot (2N-1)}{N!}2^{N} \\ &= \frac{1}{N+1}\frac{1\cdot 3\cdot 5\cdot\cdot\cdot (2N-1)}{N!}\frac{2\cdot 4\cdot 6\cdot\cdot\cdot 2N}{1\cdot 2\cdot 3\cdot\cdot\cdot N} \\ &= \frac{1}{N+1}\binom{2N}{N} \end{align}$$

于是我们得到结论，具有 $N+1$ 个虚拟节点的二叉树的个数为 $\frac{1}{N+1}\binom{2N}{N}$。另一方面，前面我们提到一棵 N 节点的树，就等同于一棵具有 N 个内部节点和 N + 1 个虚拟节点的树。于是 $T_{N}$ 也给出了具有 $N$ 个节点的二叉树的棵数。

总结

本文我们讨论了有 $N+1$ 个虚拟节点的二叉树的个数，类似的树上的计数是分析树上算法的基础问题。

基于生成函数的解决过程可以分为三步，第一步是找到生成函数满足的方程，第二步是求解方程得到生成函数，第三步是将生成函数展开取$z^{N}$项的系数。其中最关键的是第一步，只要得到了生成函数满足的方程，不管是微分方程还是函数方程，后续的过程就比较好解决了。

从组合对象找到生成函数满足的方程时，有间接方法和直接方法，本文我们进行了对比，可以看到直接方法更有优越性，直接就可以得到方程，避免了从递推关系出发去凑性质的过程。

最终我们得到了结果：具有 $N+1$ 个虚拟节点的二叉树的个数，也就是具有 $N$ 个节点的二叉树的个数为 $T_{N} = \frac{1}{N+1}\binom{2N}{N}$。

后续还有一个重要问题是 $N \rightarrow\infty$ 时 $T_{N}$ 的渐近估阶，这关系到树上的很多算法的时间复杂度。套用斯特林公式后，可以给出大致的结论 $T_{N} \approx \frac{4^{N}}{N\sqrt{\pi N}}$，更细致的估阶之后我们再继续讨论。

---