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

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

尼克

发布： 2025-10-05 21:20:02

原创

848人浏览过

答案是递归和层序遍历均可统计二叉树叶子节点：递归法判断节点为空返回0，为叶子返回1，否则递归左右子树；层序遍历用队列逐个检查节点是否为叶子并计数，二者均需判断左右孩子为空且处理空树边界。

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

在C++中统计二叉树的叶子节点数量，通常采用递归或层序遍历的方法。叶子节点是指没有左子树和右子树的节点（即左右孩子都为空）。

递归方法统计叶子节点

递归是最直观的方式。从根节点开始，判断当前节点是否为叶子节点：

如果当前节点为空，返回0。
如果当前节点的左右子节点都为空，说明是叶子节点，返回1。
否则，递归计算左子树和右子树的叶子节点数量并相加。

示例代码：

Superflow Rewrite

AI辅助高效网站设计、协作、注释工具，迭代和发布网站的最快方式

查看详情

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
<p>int countLeaves(TreeNode* root) {
if (!root) return 0;
if (!root->left && !root->right) return 1;
return countLeaves(root->left) + countLeaves(root->right);
}</p>

登录后复制

层序遍历（广度优先）统计叶子节点

使用队列进行层序遍历，逐个检查每个节点是否为叶子节点。

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

将根节点入队。
出队一个节点，判断是否为叶子节点，是则计数加1。
将其非空的左右子节点入队。
直到队列为空。

示例代码：

#include <queue>
<p>int countLeavesBFS(TreeNode* root) {
if (!root) return 0;</p><pre class='brush:php;toolbar:false;'>std::queue<TreeNode*> q;
q.push(root);
int count = 0;

while (!q.empty()) {
    TreeNode* node = q.front();
    q.pop();

    if (!node->left && !node->right) {
        count++;
    }

    if (node->left) q.push(node->left);
    if (node->right) q.push(node->right);
}
return count;

登录后复制

}