一个关于二叉树问题的证明

回家路上，跟 yg 大佬讨论了一个问题：对于一棵二叉树，其拥有两个儿子的节点个数为 $n$，要求的是叶子节点的个数。答案应该是 $n+1$，下面给出我的证明：

这是我一开始想到的方法：

首先对于一棵满二叉树（深度为 k，且有 $2^{k+1}-1$ 个节点的二叉树），正确性显然。打过线段树的都知道，对于一个节点 x，我们可以用 x<<1 表示其左儿子，x<<1|1 表示其右儿子。我们可以把一棵满二叉树用类似线段树的方法标号，如果标号最大的有两个儿子的节点编号为 $x$，则其右儿子编号为 $2x+1$，不难发现其右儿子是编号最大的节点，所以该树一共有 $2x+1$ 个节点，而有 $x$ 个有两个儿子的节点，所以叶子节点有 $x+1$ 个。

那么我们考虑一棵有 $x$ 个有两个儿子的节点的二叉树，并设它的叶子节点有 $y$ 个。那么如果我们从该树中删除一个非根叶子节点：

• 如果该节点的父亲只有一个儿子，那么其有两个儿子节点的节点数不变，又由于少了一个叶子节点，但其父亲变成了一个叶子节点，所以叶子节点的总数也不变。
• 如果该节点的父亲有两个儿子，那么少了一个有两个儿子节点的节点，当然，也少了一个叶子节点，于是原来的 $x$ 变成了 $x-1$，原来的 $y$ 变成了 $y-1$。

综上，如果有一颗二叉树其拥有两个儿子的节点个数为 $n$，其叶子节点的个数为 $n+1$，任意删除一个非根叶子节点，设现在其拥有两个儿子的节点个数为 $n$，那其叶子节点的个数仍为 $n+1$。

所以我们对满二叉树大力删点即可。

后来又想到了一种更简洁的方法（其实是一样的，只是过程逆了一下）：

考虑一棵只有根节点的树，显然它是二叉树，拥有两个儿子的节点的个数为 0，叶子节点的个数为 1，成立。

考虑对一颗二叉树加点：

• 如果作为一个叶子节点的儿子，那么其有两个儿子节点的节点数不变，叶子节点数也不变。
• 如果作为只有一个儿子的节点的另一个儿子，那么多了一个有两个儿子节点，也多了一个叶子结点。

于是从根节点开始大力添叶子即可。

感觉归纳法挺神奇的，不仅能证明线性的命题，还能证非线性的。