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

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

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

递归方法统计叶子节点

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

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

示例代码：

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;

}

关键点说明

无论是递归还是遍历方式，核心在于准确判断叶子节点：node->left == nullptr && node->right == nullptr。注意边界情况，如空树返回0。

递归写法简洁，适合理解；BFS适合避免深度过大导致栈溢出的场景。

基本上就这些，不复杂但容易忽略空指针判断。