用递归算法统计二叉树的叶结点个数

递归算法是一种自己调用自己的算法，对于统计二叉树的叶结点个数，可以使用递归算法来实现。具体步骤如下：

1. 如果当前节点为NULL，返回0。
2. 如果当前节点的左右子节点都为NULL，说明当前节点是叶子节点，返回1。
3. 递归计算当前节点的左子树中叶结点的个数。
4. 递归计算当前节点的右子树中叶结点的个数。
5. 将步骤3和步骤4的结果相加，即为当前二叉树中叶结点的个数。

下面是具体的实现代码：

int countLeafNodes(TreeNode* root) {
    if(root == NULL) {
        return 0;
    }
    if(root->left == NULL && root->right == NULL) {
        return 1;
    }
    int leftLeafNodes = countLeafNodes(root->left);
    int rightLeafNodes = countLeafNodes(root->right);
    return leftLeafNodes + rightLeafNodes;
}

其中，`TreeNode` 表示二叉树节点的结构体，包含 `val`、`left` 和 `right` 三个成员变量，分别表示节点的值、左子节点和右子节点。

相关问题

一、问题描述 已知一棵二叉树,求该二叉树的叶结点的个数 、基本要求 (1)采用二叉链表存储二叉树。 (2)采用递归算法求二叉树中叶结点个数。 (3) 采用非递归算法求二叉树中叶结点个数 、设计提示 1.数据结构设计 根据“基本要求”,二叉树采用二叉链表存储结构 2.功能设计 完成该实验至少涉及以下 4 个功能: (1) 创建二叉树。(2)显示二叉树.用于了解创建的二叉树是否正确。 (3)采用递归算法求叶结点个数。 (4)采用非递归算法求叶结点个数

二、解决方案

1.数据结构设计

二叉树采用二叉链表存储结构，每个节点包含三个成员变量：data表示节点的数据域，left表示节点的左子树指针，right表示节点的右子树指针。

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

2.功能设计

(1) 创建二叉树。

采用递归方式创建二叉树，输入-1表示该节点为空。

TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

(2) 显示二叉树。

采用前序遍历方式显示二叉树。

void displayTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->data << " ";
    displayTree(root->left);
    displayTree(root->right);
}

(3) 采用递归算法求叶结点个数。

如果当前节点为空，返回0；如果当前节点为叶子节点，返回1；否则递归计算左子树和右子树的叶子节点个数之和。

int countLeafNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

(4) 采用非递归算法求叶结点个数。

采用栈来存储节点，先将根节点入栈。每次取出栈顶元素，如果该元素为叶子节点，则计数器加1，否则将其左右子节点依次入栈，直到栈为空。

int countLeafNodesNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    stack<TreeNode*> s;
    s.push(root);
    int count = 0;
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (node->left == NULL && node->right == NULL) {
            count++;
        } else {
            if (node->right != NULL) {
                s.push(node->right);
            }
            if (node->left != NULL) {
                s.push(node->left);
            }
        }
    }
    return count;
}

三、完整代码

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

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

TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

void displayTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->data << " ";
    displayTree(root->left);
    displayTree(root->right);
}

int countLeafNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

int countLeafNodesNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    stack<TreeNode*> s;
    s.push(root);
    int count = 0;
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (node->left == NULL && node->right == NULL) {
            count++;
        } else {
            if (node->right != NULL) {
                s.push(node->right);
            }
            if (node->left != NULL) {
                s.push(node->left);
            }
        }
    }
    return count;
}

int main() {
    TreeNode* root = createTree();
    displayTree(root);
    cout << endl;
    cout << "Number of leaf nodes (recursive): " << countLeafNodes(root) << endl;
    cout << "Number of leaf nodes (non-recursive): " << countLeafNodesNonRecursive(root) << endl;
    return 0;
}

用非递归算法求二叉树的叶结点个数c

可以使用迭代法（非递归）实现二叉树的叶子节点个数。具体步骤如下：

1. 定义一个栈来存储节点指针。

2. 从根节点开始，将根节点指针入栈。

3. 循环遍历栈中的节点指针，如果该节点是叶子节点，则叶子节点个数加1；否则，将该节点的左右子节点指针分别入栈。

4. 直到栈为空，遍历结束，返回叶子节点个数。

以下是C++代码实现：

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

    stack<TreeNode*> st;
    st.push(root);
    int count = 0;

    while (!st.empty()) {
        TreeNode* cur = st.top();
        st.pop();
        if (cur->left == nullptr && cur->right == nullptr) {
            count++;
        } else {
            if (cur->left) st.push(cur->left);
            if (cur->right) st.push(cur->right);
        }
    }
    return count;
}

注：这里假设树节点的定义为 `TreeNode`，包含 `left` 和 `right` 分别表示左右子节点的指针。