图中把每个节点按孩子数量分类，再用两种方法数同一棵树的边。
一棵二叉树有九个叶节点、四个只有一个孩子的节点，能不能算出总节点数？这类题不需要猜树的形状，关键是把“节点分几类”和“树一共有几条边”联系起来。先说明这里的二叉树，每个节点最多两个孩子，并不是每个非叶节点都必须有两个孩子。
先定义三类节点
用 n0 表示没有孩子的节点数，也就是叶子数；n1 表示恰好一个孩子的节点数；n2 表示恰好两个孩子的节点数。节点总数 n 等于 n0+n1+n2，因为每个节点必然属于且只属于其中一类。
这里的度指孩子数量，也叫出度，不是无向图里把父边也算进去的邻接度。若把有父有一个孩子的节点算成度二，后面的式子就会完全换一个含义。面试时先澄清这个词，比急着套公式更重要。
讨论还要求树非空、有限、连通且没有环。空树需要单独处理，森林有多个根，含环结构更不是树。公式适用对象不清楚，推导再漂亮也无法保证结论。
第一种数边：按父子关系数
一类节点没有孩子，贡献零条向下边；一类节点有一个孩子，贡献一条；一类节点有两个孩子，贡献两条。把所有节点的出边相加，得到边数 E=n1+2n2。
每条父子边恰好由它的父节点统计一次，不会重复，也不会漏掉。树是否倾斜、左右孩子怎样分布，都不影响这次计数。它只用到了每个节点的孩子数量。
第二种数法从节点看：非空树里除根之外，每个节点恰好有一个父节点，因此边数也等于 n-1。把两种数法指向同一个 E，才有接下来消元的依据。
把两个式子放在一起
代入 n=n0+n1+n2，可得 n0+n1+n2-1=n1+2n2。两边减去 n1 和一个 n2，就得到 n0=n2+1。注意，n1 消失了，不是说树里没有单孩子节点，而是这类节点同时为节点总数和边总数各增加一。
因此，叶子数比双孩子节点数恰好多一。回到自设例子，n0 为九，所以 n2 为八；再加四个单孩子节点，总节点数为二十一。无需知道这四个节点插在哪条路径上，只要描述确实是一棵符合条件的树，计数关系就成立。
这个结果也提供反向检查。如果有人给出九个叶子却只有七个双孩子节点，在普通非空二叉树定义下就不一致，需要重新检查统计口径，而不是继续计算一个看起来合理的总数。
几个边界有助于理解
只有一个根节点时，n0 为一，n2 为零，公式成立。一条长链上，只有末端是叶子，中间节点大多是单孩子节点，同样满足一等于零加一。它说明叶子数不能单独确定总节点数，因为链可以继续变长。
如果额外限定每个非叶节点都有两个孩子，就有 n1=0，进而 n=2n0-1。只有在这个额外条件下，叶子数才能直接确定总节点数。不要把这条特殊结论用于一般二叉树。
树的高度也不能由这些分类计数唯一推出。同样的节点数和叶子数，可能对应不同的排列形状。计数公式回答的是数量约束，不是具体结构，更不是最坏查找长度。
从公式回到算法验证
若输入是一组父子关系，可以先检查每个节点孩子数不超过二、根的数量、连通性和环，再统计 n0、n1、n2。只算出公式成立，也不足以证明输入真的是一棵树；一些非法结构可能恰好凑出同样的数量关系。
小规模枚举各种二叉树形状，再逐棵核对两种边计数，是有价值的实现检查。但公式对所有有限非空二叉树的依据，仍是前面“一条边恰好数一次”的推导，而不是枚举样本足够多。
下次遇到节点计数题，可以先找同一个量的两种计数方式。若把一棵树改成有两个根的二叉森林，边数从 n-1 变成什么，叶子与双孩子节点的差又会怎样改变？