空指针必须显式跳过,递归统计总有效节点数的核心是先判空再累加:若root为nullptr返回0,否则返回1+左子树节点数+右子树节点数;迭代则需pop后判空再计数,避免将nullptr误计。

递归统计总有效节点数时,空指针必须显式跳过
递归实现最直观,但新手常因忽略 nullptr 判断导致段错误或重复计数。核心逻辑是:只对非空节点递归,并在进入递归前累加当前节点(即 +1)。若写成先递归再判断,就可能把 nullptr 当作有效节点传入,触发未定义行为。
- 正确写法:先检查
root == nullptr,是则返回 0;否则返回1 + countNodes(root->left) + countNodes(root->right) - 常见错误:漏掉边界判断,或把
countNodes(nullptr)当作合法调用——C++ 不会自动跳过,而是直接解引用崩溃 - 注意:该递归不区分“有效节点”与“占位空节点”,只要内存中真实存在的
TreeNode*指向有效对象,就算一个节点;所谓“有效”在此语境下即非空且已分配
迭代实现需手动维护栈或队列,避免隐式调用栈干扰计数
迭代本质是模拟系统调用栈行为,但必须自己管理节点访问顺序和计数时机。用 std::stack 或 std::queue 都可以,区别只在遍历序(DFS vs BFS),不影响总数。关键陷阱在于:不能在 push 时就 ++count,因为此时节点尚未确认“有效”(比如刚 push 的 left 指针可能是 nullptr)。
- 安全做法:pop 出节点后,先判空;非空则 ++count,再将左右子指针(无论是否为空)push 进栈/队列
- 错误模式:push 前就 ++count ——会导致把
nullptr占位符也计入,结果偏大 - 性能提示:
std::stack在 DFS 场景下局部性更好;std::queue内存分配稍多,但逻辑更直白,不易错
递归与迭代的时空开销差异实际取决于树形态
教科书常说“递归空间复杂度 O(h),迭代 O(n)”,但这仅在最坏单链场景下成立。现实中,若树接近平衡,递归深度 h ≈ log n,而迭代容器在 BFS 中峰值容量可达 O(n/2)(满二叉树最后一层);DFS 迭代栈最大深度同样为 O(h)。所以不能一概而论。
- 递归优势:代码短、语义清晰,编译器可能做尾递归优化(但 C++ 标准不保证,且本例无法尾递归)
- 迭代优势:可控栈大小,避免 deep recursion 导致的 stack overflow(尤其在嵌入式或栈限制严的环境)
- 实测建议:对深度 > 1000 的树,优先选迭代;对小树或开发调试阶段,递归更易验证逻辑
统计逻辑一致,但“有效节点”定义必须提前对齐
所谓“有效节点”,不同项目可能有不同含义:有的指非空且 val 合法(如非哨兵值);有的指内存已分配且指针可解引用;还有的要求满足特定业务条件(如 val > 0)。递归和迭代都只是计数工具,真正的过滤逻辑必须显式嵌入。
立即学习“C++免费学习笔记(深入)”;
- 例如:若要求只统计
val != -1的节点,则递归中要写return (root->val != -1 ? 1 : 0) + ...;迭代中要在 pop 后加 if 判断 - 别依赖
root->left或root->right是否为空来推断父节点有效性——它们只是指针,不反映父节点状态 - 最容易被忽略的是:构造树时用
new TreeNode(0)初始化的节点,即使val为 0,也是有效节点;而未 new、仅声明TreeNode* p = nullptr的不算


















