二叉树节点数计算

二叉树是一种基础的数据结构，它由若干个节点组成，每个节点包含一个值和两个子节点指针。如何计算二叉树的节点数是一个常见的问题，但是其背后涉及到多个角度的思考。

角度1：递归计算

最常见的计算二叉树节点数的方法是递归计算，即将整个树分为左子树和右子树两部分，节点数等于左子树节点数加右子树节点数再加根节点，公式为 N = Nleft + Nright + 1。其中，N代表二叉树的节点数，Nleft代表左子树的节点数，Nright代表右子树的节点数。

这种递归计算的方法有两个前提条件，一是二叉树的每个节点都不为空，二是每个节点只有左右两个子节点。如果有一个节点为空或一个节点拥有超过两个子节点，则需要进行特殊处理。

代码实现如下：

```

int countNodes(TreeNode* root) {

if (root == NULL) {

return 0;

}

return countNodes(root->left) + countNodes(root->right) + 1;

}

```

递归计算的时间复杂度为O(n)，其中n为二叉树的节点数。

角度2：完全二叉树节点数计算

完全二叉树是一种特殊的二叉树，每一层从左至右都是满的，最后一层从左至右可能存在空的节点。对于一个完全二叉树，很容易计算其节点数，公式为 N = 2^h - 1，其中h为树的高度。

具体的证明过程如下：

设一棵完全二叉树的高度为h，那么它的叶子节点数为2^(h-1) ~ 2^h - 1，它的倒数第二层节点数为2^(h-2) ~ 2^(h-1)-1，一直向上层层计算，最终得到节点数为：

```

2^0 + 2^1 + 2^2 + ... + 2^(h-1) = 2^h - 1

```

代码实现如下：

```

int countNodes(TreeNode* root) {

int h = 0;

TreeNode* node = root;

while (node != NULL) {

h++;

node = node->left;

}

int count = pow(2, h-1) - 1;

int left = 0, right = pow(2, h-1) - 1;

while (left <= right) {

int mid = (left + right) / 2;

if (exist(root, h-1, mid)) {

left = mid + 1;

} else {

right = mid - 1;

}

}

return count + left;

}

bool exist(TreeNode* root, int depth, int idx) {

int left = 0, right = pow(2, depth)-1;

TreeNode* node = root;

for (int i = 0; i < depth; i++) {

int mid = (left + right) / 2;

if (idx <= mid) {

node = node->left;

right = mid;

} else {

node = node->right;

left = mid + 1;

}

}

return node != NULL;

}

```

完全二叉树节点数计算的时间复杂度为O(log^2n)。

角度3：不完全二叉树节点数计算

如果二叉树不是完全二叉树，则不能使用上面的公式来计算节点数。对于一般的二叉树，我们可以使用层次遍历来计算节点数。

具体的实现过程如下：

```

int countNodes(TreeNode* root) {

if (root == NULL) {

return 0;

}

int count = 0;

queue nodes;

nodes.push(root);

while (!nodes.empty()) {

TreeNode* node = nodes.front();

nodes.pop();

count++;

if (node->left != NULL) {

nodes.push(node->left);

}

if (node->right != NULL) {

nodes.push(node->right);

}

}

return count;

}

```

不完全二叉树节点数计算的时间复杂度为O(n)。

综上所述，计算二叉树节点数有多种方法，可以从递归计算、完全二叉树节点数计算和不完全二叉树节点数计算三个角度进行思考。其中递归计算是最常见的方法，时间复杂度为O(n)；完全二叉树节点数计算可以利用满二叉树的特性，时间复杂度为O(log^2n)；不完全二叉树节点数计算则需要用到层次遍历，时间复杂度为O(n)。