递归统计节点数最简洁但易栈溢出，需空指针检查；迭代法（bfs/dfs）避免栈溢出，morris遍历不适用于只读场景；完全二叉树可用o(log²n)优化，但非通用。
递归统计二叉树节点数：简洁但要注意栈溢出
直接写 countNodes(root) 递归函数是最自然的做法：空节点返回 0，否则返回 1 + countNodes(root->left) + countNodes(root->right)。逻辑清晰，代码三行搞定。
但实际用在深度超过 10⁴ 的退化链状树上，会触发栈溢出——C++ 默认线程栈通常只有 1~8MB，每次递归调用压入栈帧（含返回地址、局部变量、寄存器保存等），深递归开销不可忽视。
常见错误是没加空指针检查，比如直接访问 root->left 而未判 root == nullptr，运行时抛 segmentation fault。
使用场景：开发调试、树高可控（如平衡二叉搜索树、AVL、红黑树的常规操作）、教学演示。
迭代统计节点数：用栈或队列避免栈溢出
迭代本质是手动模拟递归调用栈，推荐用 std::stack<treenode></treenode> 做 DFS 或 std::queue<treenode></treenode> 做 BFS。两者时间复杂度都是 O(n)，空间复杂度取决于树宽或树高。
BFS 迭代更直观：初始化队列 push root，每次 pop 一个节点，若非空则计数加 1，并将左右子节点 push 入队。注意必须判 node != nullptr 才 push 子节点，否则队列里混入空指针，后续解引用崩掉。
DFS 迭代稍易错：先 push root，进循环后 pop，若非空则计数加 1，再按「右左」顺序 push（保证左子树先处理，与递归顺序一致）。漏掉任一子节点的 push，结果就少算。
性能影响：BFS 在完全二叉树中峰值队列长度 ≈ 最后一层节点数（O(n/2)）；DFS 迭代峰值栈大小 ≈ 树高（O(h)），对倾斜树仍可能达 O(n)。
要不要用 Morris 遍历做 O(1) 空间迭代？
Morris 遍历能将空间降到 O(1)，但它需要临时修改树结构（建立/拆除线索），统计节点数这种只读操作不值得冒风险：一旦中途异常退出，树可能处于损坏状态，后续逻辑全错。
除非你明确知道输入树是只读且可被篡改的，或者在嵌入式等内存极端受限环境（RAM
容易踩的坑：while 循环里忘记恢复 current->right = nullptr，导致下次遍历或调试时指针乱跳；或误把 current->left == nullptr 当作终止条件，漏掉右子树。
当树是完全二叉树时，有更快的 O(log²n) 解法
如果题目明确给出「完全二叉树」前提（如 LeetCode 222），可以不用遍历全部节点：通过不断检查最左、最右路径长度，判断左右子树是否满，再递归较浅的一边。核心函数是 getDepth()，反复走 left 指针即可。
但这属于特例优化，和通用统计无关。强行套用在普通二叉树上结果错误——比如某层中间缺一个节点，getDepth(left) 和 getDepth(right) 相等，但右子树根本不满，直接返回 2^h - 1 就漏算了。
判断是否为完全二叉树本身就要 O(n)，所以这个优化只适用于输入已知满足条件的场景，不能当作通用方案。
真正要落地，优先写带空指针防护的递归版本用于开发；上线前若担心深度，换 BFS 迭代并加计数上限断言（如 if (count > 1e6) throw std::runtime_error("tree too large")）；其余花活，先确认需求是否真需要。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
