递归计算二叉树节点总数的核心是“当前节点+左子树节点数+右子树节点数”，需先判空再累加1，时间复杂度O(n)，空间复杂度O(h)；迭代法用栈模拟，避免栈溢出；完全二叉树可优化至O(log²n)。
递归计算节点总数最直接
二叉树节点总数本质上是“当前节点 + 左子树节点数 + 右子树节点数”，递归天然匹配这个结构。只要树不为空，就累加 1 再递归左右子树；空节点返回 0。
常见错误是忘记判空导致 nullptr 解引用崩溃，或漏掉当前节点的 +1：
int countNodes(TreeNode* root) {
if (!root) return 0; // 必须先判空
return 1 + countNodes(root->left) + countNodes(root->right);
}-
TreeNode*是典型节点指针类型，实际使用时需确认你的节点结构名（如Node*或BSTNode*） - 时间复杂度
O(n)，空间复杂度O(h)（h 为树高，最坏退化成链表时为O(n)） - 不要写成
return countNodes(root->left) + countNodes(root->right)—— 这会漏掉根节点
迭代方式用栈模拟递归
当树很深、担心栈溢出时，改用显式栈避免系统调用栈压栈。核心逻辑不变：每弹出一个节点，计数器加 1，再把它的非空子节点压入栈。
容易踩的坑是子节点入栈顺序不重要，但必须检查是否为 nullptr，否则会往栈里塞无效指针：
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
int countNodes(TreeNode* root) {
if (!root) return 0;
stack<TreeNode*> s;
s.push(root);
int count = 0;
while (!s.empty()) {
TreeNode* node = s.top(); s.pop();
count++; // 当前节点计入
if (node->left) s.push(node->left);
if (node->right) s.push(node->right);
}
return count;
}- 用
stack而不是queue——这里不需要层序遍历，DFS/BFS 都能数清节点，选栈更贴近递归语义 - 如果用
queue，只需把stack换成queue，top()改成front()，pop()前加pop() - 迭代写法空间复杂度仍是
O(h)（栈中最多存一条路径上的节点），不是O(1)
完全二叉树可优化到 O(log²n)
如果题目明确说“完全二叉树”（complete binary tree），就不能套用通用方法——利用其结构规律：除最后一层外全满，且最后一层靠左。此时可通过比较左右子树高度，决定哪边是满二叉树，跳过部分遍历。
关键点在于：满二叉树节点数 = 2^h - 1，而完全二叉树的左右子树至多差一层：
int countNodes(TreeNode* root) {
if (!root) return 0;
TreeNode* left = root, *right = root;
int heightLeft = 0, heightRight = 0;
while (left) { left = left->left; heightLeft++; }
while (right) { right = right->right; heightRight++; }
if (heightLeft == heightRight)
return (1 << heightLeft) - 1; // 满二叉树：2^h - 1
return 1 + countNodes(root->left) + countNodes(root->right);
}- 必须严格满足完全二叉树定义才适用，普通二叉树用这个反而更慢
1 等价于 <code>pow(2, heightLeft)，但位运算更快且避免浮点误差- 每次递归只走一边，总时间复杂度
O(log²n)，因为每层最多做一次O(log n)的高度探测
带计数成员变量的树类设计
如果频繁查询节点总数（比如在插入/删除后实时维护），硬算每次都是 O(n)，不如在树结构里缓存总数。这时需保证所有修改操作同步更新计数器。
典型错误是只在插入时加 1，却忘了删除时减 1，或子树旋转、合并等操作后未重算：
struct BST {
TreeNode* root;
int size; // 缓存节点总数
BST() : root(nullptr), size(0) {}
void insert(int val) {
root = insertHelper(root, val);
size++; // 插入成功才加
}
void erase(int val) {
if (find(val)) {
root = eraseHelper(root, val);
size--; // 删除成功才减
}
}
};-
size是易错点：必须与所有变更操作严格耦合，否则数值迅速失真 - 适用于读多写少场景；若写操作极频繁，维护开销可能抵消查询收益
- 序列化/反序列化时别忘了保存和恢复
size字段，否则重建后计数归零
实际用哪个方法，取决于树的形态、调用频率和是否允许修改结构。通用场景优先写递归，深度隐患明显时换迭代，确定是完全二叉树再上高度探测，高频查询且可控写入才考虑缓存 size。
