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

二叉树的叶子节点是指没有孩子的节点，即左孩子指针为空并且右孩子指针也为空的节点。在二叉链表存储结构中，我们可以采用递归或迭代的方式来遍历二叉树并计算叶子节点的数量。

**递归方法（C++）**:

#include <iostream>
using namespace std;

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

int countLeaves(TreeNode* root) {
    if (root == nullptr) return 0; // 遇到空节点返回0
    else if (root->left == nullptr && root->right == nullptr) // 叶子节点直接返回1
        return 1;
    else
        return countLeaves(root->left) + countLeaves(root->right); // 继续递归处理左右子树
}

int main() {
    // 创建一个示例二叉树
    TreeNode* tree = new TreeNode(1);
    tree->left = new TreeNode(2);
    tree->right = new TreeNode(3);
    tree->left->left = new TreeNode(4);
    tree->left->right = new TreeNode(5);

    cout << "叶节点个数: " << countLeaves(tree) << endl;

    return 0;
}

**非递归方法（C++）**:
这里我们使用栈来模拟递归过程。首先将根节点压入栈，然后不断从栈中取出节点直到栈为空。对于每个取出的节点，如果它没有孩子，则计数加一。

#include <iostream>
#include <stack>
using namespace std;

// ... (TreeNode结构同上)

int countLeavesIterative(TreeNode* root) {
    stack<TreeNode*> nodeStack;
    int leafCount = 0;

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

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

        if (current->left == nullptr && current->right == nullptr) { // 叶子节点
            leafCount++;
        }
        
        if (current->right != nullptr) {
            nodeStack.push(current->right);
        }
        if (current->left != nullptr) {
            nodeStack.push(current->left);
        }
    }

    return leafCount;
}

int main() {
    // ... (创建示例二叉树同上)
    cout << "叶节点个数: " << countLeavesIterative(tree) << endl;

    return 0;
}