C++如何实现二叉树节点总数计算

递归计算二叉树节点总数的核心是“当前节点+左子树节点数+右子树节点数”，需先判空再累加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++免费学习笔记（深入）”；

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。