二叉树总结点计算方法
二叉树是一种常用的数据结构，其节点数量的计算方法是非常重要的。在本文中，将从多个角度出发，探讨二叉树总结点计算方法。
一、递归计算法
递归计算法是最常用的二叉树总结点计算方法。其基本思路是将当前二叉树的节点数等于其左子树节点数加右子树节点数加1。具体操作如下：
```
int countNodes(TreeNode* root) {
if(!root) return 0;
int left = countNodes(root->left);
int right = countNodes(root->right);
return left + right + 1;
}
```
该算法的时间复杂度为O(N)，空间复杂度为O(H)，其中H是二叉树的树高。
二、迭代计算法
迭代计算法是递归计算法的一种变体，其基本思路是将递归转为迭代。具体操作步骤如下：
```
int countNodes(TreeNode* root) {
if(!root) return 0;
stack
stk.push(root);
int res = 0;
while(!stk.empty()) {
TreeNode* curr = stk.top();
stk.pop();
res++;
if(curr->left) stk.push(curr->left);
if(curr->right) stk.push(curr->right);
}
return res;
}
```
该算法的时间复杂度为O(N)，空间复杂度也为O(N)，其中N是二叉树的总节点数。
三、数学公式
通过公式推导，我们可以得到以下两个计算公式：
1. 完全二叉树节点数公式：
```
int countNodes(TreeNode* root) {
if(!root) return 0;
int level = 0;
TreeNode* node = root;
while(node->left) {
level++;
node = node->left;
}
int low = 1 << level, high = (1 << (level+1)) - 1;
while(low < high) {
int mid = (high - low + 1) / 2 + low;
if(exists(root, level, mid)) low = mid;
else high = mid - 1;
}
return low;
}
bool exists(TreeNode* root, int level, int k) {
int bits = 1 << (level - 1);
TreeNode* node = root;
while(node && bits > 0) {
if(!(bits & k)) node = node->left;
else node = node->right;
bits >>= 1;
}
return node != nullptr;
}
```
2. 普通二叉树节点数公式：
```
int countNodes(TreeNode* root) {
if(!root) return 0;
int left = countLevel(root->left);
int right = countLevel(root->right);
if(left == right) return countNodes(root->right) + (1 << left);
else return countNodes(root->left) + (1 << right);
}
int countLevel(TreeNode* root) {
int level = 0;
while(root) {
level++;
root = root->left;
}
return level;
}
```
这两个计算公式的时间复杂度都为O((logN)^2)，空间复杂度为O(1)，其中N是二叉树的总节点数。
四、总结
经过以上分析，我们可以发现，在不同的场景下，选择不同的计算方法是很重要的。递归计算法和迭代计算法虽然简单易懂，但其时间复杂度和空间复杂度都较高；而基于数学公式推导的计算方法虽然更加高效，但需要对二叉树节点数的特殊情况分别处理，容易出现错误。因此，在实际问题中，需要根据问题的需要，选择合适的计算方法。
