c++中如何计算二叉树节点数量_c++二叉树节点数量计算方法-C++-PHP中文网

c++中如何计算二叉树节点数量_c++二叉树节点数量计算方法

下次还敢

发布： 2025-09-25 15:57:01

原创

589人浏览过

答案是使用递归或迭代方法计算二叉树节点数：递归通过左右子树相加加1实现，迭代用栈模拟遍历计数。

c++中如何计算二叉树节点数量_c++二叉树节点数量计算方法

在C++中计算二叉树的节点数量，通常使用递归方法。核心思想是：当前节点的数量等于左子树节点数 + 右子树节点数 + 1（当前节点本身）。

定义二叉树节点结构

首先需要定义二叉树的节点结构，一般如下：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

登录后复制

递归计算节点数量

通过递归遍历整棵树，统计所有节点。如果节点为空，返回0；否则返回左右子树节点总数加1。

int countNodes(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    return countNodes(root->left) + countNodes(root->right) + 1;
}

登录后复制

非递归方法（使用栈模拟遍历）

也可以用迭代方式避免递归带来的栈溢出风险，使用栈或队列进行层序或前序遍历，每访问一个节点计数加1。

算家云

高效、便捷的人工智能算力服务平台

查看详情

立即学习“C++免费学习笔记（深入）”；

#include <stack>
int countNodesIterative(TreeNode* root) {
    if (root == nullptr) return 0;
    std::stack<TreeNode*> stk;
    stk.push(root);
    int count = 0;
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        if (node) {
            count++;
            stk.push(node->right);
            stk.push(node->left);
        }
    }
    return count;
}

登录后复制

基本上就这些。递归写法简洁易懂，适合大多数场景；迭代方法更安全，适合深度较大的树。根据实际需求选择即可。

以上就是c++++中如何计算二叉树节点数量_c++二叉树节点数量计算方法的详细内容，更多请关注php中文网其它相关文章！