递归统计总节点数最直观但需防栈溢出，空节点返回0，否则返回左右子树节点数加1；迭代法用队列或栈避免爆栈，时间复杂度均为o(n)，空间复杂度分别为o(w)和o(h)。
递归统计总节点数：简洁但要注意栈溢出
直接写 countNodes 递归函数是最直观的做法：空节点返回 0，否则返回左子树节点数 + 右子树节点数 + 1。但实际用时得小心深度过大的树——比如退化成链表的二叉树（height ≈ n），递归调用栈可能爆掉。
常见错误是漏判空指针，或把 nullptr 当作有效节点计数：
int countNodes(TreeNode* root) {
if (!root) return 0; // 必须先判空
return countNodes(root->left) + countNodes(root->right) + 1;
}
- 适用于普通二叉树，时间复杂度
O(n)，空间复杂度O(h)（h是树高） - 如果编译器不支持尾递归优化，哪怕树只有 10⁵ 层，也可能触发
stack overflow - 不能直接套用在完全二叉树上——那里有更优的
O(log²n)解法，但那是另一回事
迭代统计总节点数：用栈或队列避免爆栈
迭代本质是手动模拟递归过程，关键在于选哪种遍历顺序无关紧要（前/中/后/层序），只要每个节点访问一次就行。用栈模拟 DFS 更接近递归逻辑；用队列做 BFS（层序）则更易理解、不易写错。
容易踩的坑是忘记把子节点入栈/入队，或者重复访问同一节点：
int countNodes(TreeNode* root) {
if (!root) return 0;
int cnt = 0;
queue<treenode> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
cnt++;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return cnt;
}</treenode>
- 空间复杂度变成
O(w)，其中w是最大宽度（BFS 最坏情况是满二叉树最后一层，约n/2） - DFS 迭代版要用栈，注意压栈顺序：先右后左，才能保证左子树先处理（可选，不影响计数结果）
- 别在循环里漏掉
cnt++，这是最常发生的低级错误
什么时候该用递归，什么时候必须迭代？
没有绝对标准，取决于你对输入规模和环境的掌控程度。
- 本地调试小数据（
n ）、树高可控（<code>h ）→ 递归更干净 - 在线 OJ 或嵌入式环境栈空间受限 → 迭代更稳妥，尤其 BFS 对内存使用更可预期
- 如果已有现成的遍历框架（比如你正在写一个通用遍历器），复用迭代逻辑比硬塞递归更自然
- 某些 C++ 编译器（如 MSVC）默认栈大小仅 1MB，10⁶ 层的链式树会直接崩溃，而迭代版只消耗堆内存
别忽略空树和单节点这种边界情况
所有实现都必须显式处理 root == nullptr，否则运行时崩溃或返回随机值。测试时至少覆盖这三组输入：
-
nullptr→ 返回0 - 单节点（
root无左右子）→ 返回1 - 两层满树（根 + 左 + 右）→ 返回
3
真实项目里，有人用 std::optional<int></int> 包一层再返回，反而增加调用方负担；不如一开始就保证接口对空输入有定义。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
