二叉树采用二叉链表存储结构，请分别用递归和非递归算法求二叉树的叶子节点的个数（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; // 叶子节点，返回1
    else return countLeaves(root->left) + countLeaves(root->right); // 递归处理左右子树
}

// 示例
int main() {
    // 创建一个简单的二叉树...
    // 然后传入根节点调用countLeaves函数
    TreeNode* tree = ...; // 实际构造的二叉树
    int leafCount = countLeaves(tree);
    std::cout << "Leaf nodes count: " << leafCount << std::endl;
    return 0;
}

**非递归方法（使用栈）：**

#include <iostream>
#include <stack>

int countLeavesNonRecursive(TreeNode* root) {
    int leafCount = 0;
    std::stack<TreeNode*> nodeStack;

    if (root != nullptr) {
        nodeStack.push(root);
    }

    while (!nodeStack.empty()) {
        TreeNode* currNode = nodeStack.top();
        nodeStack.pop();

        // 如果当前节点无左、右子节点，增加计数
        if (currNode->left == nullptr && currNode->right == nullptr) {
            leafCount++;
        }

        // 非空子节点入栈
        if (currNode->left != nullptr) {
            nodeStack.push(currNode->left);
        }
        if (currNode->right != nullptr) {
            nodeStack.push(currNode->right);
        }
    }

    return leafCount;
}

// 示例同上
int main() {
    TreeNode* tree = ...;
    int leafCount = countLeavesNonRecursive(tree);
    std::cout << "Leaf nodes count: " << leafCount << std endl;
    return 0;
}

这两种方法都会遍历整个二叉树，并对每个节点检查其是否有左右子节点，以确定是否为叶子节点。