Content #
对任何一棵二叉树,如果其叶节点数量为n0,度为 2 的节点数量为n2,即:n0=n2+1。
除了叶节点(度为 0),其他的节点度数要么为 1 要么为 2,如果假设度为 1 的节点数量是 n1,那么该二叉树的节点总数量 n = n0 + n1 + n2。
再算一算节点的总度数,节点的总度数应该等于 2*n2 + n1。
由于,节点的总数量 = 节点的总度数 + 1,就有:
节点总数量 n = 2*n2 + n1+ 1。
结合刚才的节点总数量式子,可以得到:n0 + n1 + n2 = 2n2 + n1+ 1。
两边同时减少一个 n1 和一个 n2,不难得到:n0 = n2 + 1。