回家路上，跟 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，成立。
考虑对一颗二叉树加点：
- 如果作为一个叶子节点的儿子，那么其有两个儿子节点的节点数不变，叶子节点数也不变。
- 如果作为只有一个儿子的节点的另一个儿子，那么多了一个有两个儿子节点，也多了一个叶子结点。
于是从根节点开始大力添叶子即可。
感觉归纳法挺神奇的，不仅能证明线性的命题，还能证非线性的。