完全二叉树度为2的结点数

完全二叉树是指深度为 $k$ 的二叉树，按照从上到下、从左到右的顺序依次填满节点，最后一层可以不满。如果完整地填满，则称其为满二叉树。而度为2的结点是指子节点数为2的结点，也被称为内部节点。

在完全二叉树中，内部节点的子节点数只能为0或2。因此，我们可以得出一个很明显的结论：在完全二叉树中，所有的内部节点都是度为2的节点。所以，问题转化为了求完全二叉树中度为2的节点数。

解法一：数学推导

在一个二叉树中，度为 $k$ 的节点数为 $n_k$，则该二叉树的结点数为 $N=\sum_{k=0}^{m} n_k$，其中 $m$ 为最大度数。对于度为2的节点，其子节点数量不会超过2，我们可以得到以下递归式：$n_2 = n_0-1$，$n_k=2\times n_{k-1}$（$k \ge 3$）。其中，$n_0$ 表示叶子节点的个数。

我们发现，当完全二叉树的深度为 $k$ 时，叶子节点数量 $n_0 = 2^k$。代入上述递归式，可以得到：$$

\begin{aligned}

n_2 &= n_0-1 = 2^k -1 \\

n_3 &= 2\times n_2 = 2\times (2^k-1) = 2^{k+1}-2 \\

n_4 &= 2\times n_3 = 2\times (2^{k+1}-2) = 2^{k+2}-4 \\

\dots \\

n_k &= 2^{k}-2^{k-1}

\end{aligned}

$$ 因此，完全二叉树中度为2的节点数为 $n_2+n_3+n_4+\cdots+n_k$。将上述式子代入，得到：$$

\begin{aligned}

n_2+n_3+n_4+\cdots + n_k &= 2^k-1 + (2^{k+1}-2) + (2^{k+2}-4) + \cdots + (2^k-2^{k-1}) \\

&= (2^{k+1}-1) - (k+1)2^k \\

&= (2^{\lfloor \log_2 N \rfloor+1}-1) - \left(\lfloor \log_2 N \rfloor+1 \right)2^{\lfloor \log_2 N \rfloor}

\end{aligned}

$$

解法二：递归计算

另一种求解方法是递归计算。对于一棵非空的完全二叉树，其第一个节点必定是一个度为2的节点。假设其左子树和右子树都是完全二叉树，且深度相同，那么度为2的节点数目可以递归计算出来。左子树和右子树的深度是相同的，要么都到了最大深度，要么都没到。

如果到了最大深度，那么它们的度为2的节点数也可以通过数学推导计算出来；如果还没到，那么可以递归计算左子树和右子树的度为2的节点数，然后相加即可。

具体实现过程：从根节点开始，如果一个节点为 $null$，则直接返回0；否则，返回 $1+(left?1:0)+(right?1:0)$，其中 $left$ 和 $right$ 分别表示左子树和右子树是否为空。

解法三：层次遍历

还可以通过层次遍历的方式计算完全二叉树中度为2的节点数。首先，树的第一层只有一个节点。之后每一层节点数都是前一层节点数的2倍（也就是说，每个节点都会产生两个子节点）。在每一层中，记住已经计算过的节点数量，每当计算完一层时，将计算结果累加起来，最终得到度为2的节点数。