原文链接： 硬核总结！真二叉树、满二叉树、完全二叉树的性质与概念_qq_31601743的博客-博客 https://blog.csdn.net/qq_31601743/article/details/103840143
这篇博客末尾附了一道面试题： 如果一棵完全二叉树有768个节点，求叶子节点的个数。 而没有给出具体的解答过程与答案。现在根据个人理解，写一下这道题的解答过程。
首先，这所有768个节点中，度只可能为0、1或者2，设度为0的节点数量为 n 0 n_{0} n0,度为1的节点数量为 n 1 n_{1} n1,度为2的节点数量为 n 2 n_{2} n2,则必有 768 = n 0 + n 1 + n 2 768=n_{0}+n_{1}+n_{2} 768=n0+n1+n2
由于有结论(上面博客中介绍的)
对于任何一棵非空完全二叉树，如果叶子节点的个数为 n 0 n_{0} n0,度为2的节点的个数为 n 2 n_{2} n2,则有 n 0 = n 2 + 1 n_{0}=n_{2}+1 n0=n2+1
对于这一结论的证明将附在本文后。 所以有 768 = 2 n 2 + n 1 + 1 768=2n_{2}+n_{1}+1 768=2n2+n1+1
又因为有结论
完全二叉树中，度为1的节点个数或者是0，或者是1
由奇偶性分析容易知道，这里只能取 n 1 = 1 n_{1}=1 n1=1 于是有 n 2 = ( 768 − 2 ) / 2 = 383 n_{2}=(768-2)/2=383 n2=(768−2)/2=383, n 0 = n 2 + 1 = 384 n_{0}=n_{2}+1=384 n0=n2+1=384 故答案为384。
附录： 对"对于任何一棵非空完全二叉树，如果叶子节点的个数为 n 0 n_{0} n0,度为2的节点的个数为 n 2 n_{2} n2,则有 n 0 = n 2 + 1 n_{0}=n_{2}+1 n0=n2+1"结论的证明
证明： 设该二叉树的节点总数为 n n n,则必有 n = n 0 + n 1 + n 2 n=n_{0}+n_{1}+n_{2} n=n0+n1+n2 同时由树的节点数与边数关系，设该二叉树边数为 m m m,则有 m = n − 1 m=n-1 m=n−1 同时有 m = 2 n 2 + n 1 m=2n_{2}+n_{1} m=2n2+n1 联立得 2 n 2 + n 1 = n 0 + n 1 + n 2 − 1 2n_{2}+n_{1}=n_{0}+n_{1}+n_{2}-1 2n2+n1=n0+n1+n2−1 化简即得 n 0 = n 2 + 1 n_{0}=n_{2}+1 n0=n2+1
