二叉树采用二叉链表存储数据，请分别用递归和非递归方法编写算法求二叉树的叶子结点的个数，用C++实现

在C++中，二叉树的叶子节点是没有左孩子和右孩子的节点。我们首先给出递归和非递归的思路，然后提供具体的C++代码实现。

### 递归方法：

递归的基本思想是，对于每个节点，如果它是叶子节点，则计数加一；如果不是，就对它的左右子节点递归地进行同样的操作。这里是一个递归函数的例子：

#include <iostream>

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

int countLeaves(TreeNode* root) {
    if (root == nullptr) {
        return 0; // 如果根为空，返回0
    } else if (root->left == nullptr && root->right == nullptr) { // 如果当前节点是叶子节点
        return 1;
    } else {
        return countLeaves(root->left) + countLeaves(root->right); // 否则，对左右子节点递归求和
    }
}

### 非递归方法（广度优先搜索BFS）：

非递归的方式通常需要借助队列来辅助遍历。从根节点开始，先将其入队，然后每次出队并检查是否为叶子节点，是的话计数加一，同时将左右子节点也放入队列。直到队列为空，叶子节点的数量即为结果。

#include <iostream>
#include <queue>

// ... (TreeNode结构体定义同上)

int countLeavesNonRecursive(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }

    std::queue<TreeNode*> q({root});
    int leafCount = 0;

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

        if (node->left == nullptr && node->right == nullptr) {
            leafCount++;
        }

        if (node->left != nullptr) {
            q.push(node->left);
        }
        if (node->right != nullptr) {
            q.push(node->right);
        }
    }

    return leafCount;
}