求二叉树的叶结点的个数

求二叉树的叶结点的个数可以通过遍历二叉树并统计叶节点的个数来实现。具体方法如下：

1. 如果当前节点为空，则返回0。
2. 如果当前节点没有左子树和右子树，则当前节点为叶节点，返回1。
3. 否则，递归遍历左子树和右子树，并将结果相加。

下面是一个示例代码实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def count_leaf_nodes(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)

其中，`TreeNode` 是二叉树的节点类，`count_leaf_nodes` 是求二叉树叶节点个数的函数，`root` 是二叉树的根节点。

相关问题

求二叉树中叶结点的个数、二叉树结点总数以及二叉树的深度。

### 回答1：
二叉树中叶结点的个数是指没有子节点的节点个数，可以通过遍历整个二叉树，统计叶节点的个数来得到。

二叉树结点总数是指整个二叉树中节点的总个数，可以通过遍历整个二叉树，统计节点的个数来得到。

二叉树的深度是指从根节点到最深叶节点的路径长度，可以通过递归遍历二叉树，每次记录当前节点的深度，最终得到最大深度来得到。

### 回答2：
二叉树是一种重要的树形数据结构，其中每个节点最多只有两个子节点，分别为左子节点和右子节点。二叉树可以用来存储和管理各种数据信息，如文件系统、数据库索引等。在二叉树中，叶节点是指没有子节点的节点，二叉树的深度是指从根节点到某个叶节点的最长路径长度。

要求二叉树中叶节点的个数，可以采用遍历二叉树的方法，将每个节点都进行判断，若该节点没有左右子节点，则该节点就是叶节点。可以使用递归的方式实现代码，从根节点开始遍历，当遇到叶节点时，将叶节点的个数加1。遍历完成后，即可得到二叉树中叶节点的个数。

要求二叉树结点总数，也可以采用递归的方法，从根节点开始，每个节点的总数等于左子树节点的总数加上右子树节点的总数再加上1（当前节点）。因此可以递归地计算下去，直到叶节点，这时候总数为1。最后将每个节点计数相加即可得到二叉树的结点总数。

要求二叉树的深度，同样可以采用递归的方法来实现。以该节点为根的深度等于其左子树的深度与右子树的深度之间的较大值再加上1。因此可以递归地计算下去，直到叶节点，这时候深度为1。最后将每个节点的深度计算出来，取其中的最大值即可得到二叉树的深度。

### 回答3：
二叉树是一种经典的树形数据结构，由根节点和两个子树组成，其中子树本身也是一棵二叉树。在二叉树中，叶子节点是没有子节点的节点，而非叶节点是至少有一个子节点的节点。求二叉树中的叶子节点数量、节点总数和深度是二叉树相关问题中的常见问题。

首先，要求二叉树中的叶子节点数量。我们可以通过递归遍历所有子树，找出叶子节点并计数。以下是求二叉树叶子节点个数的代码：

int countLeafNodes(BinaryTree tree) {
    if (tree == null) {
        return 0;
    }
    if (tree.left == null && tree.right == null) {
        return 1;
    }
    return countLeafNodes(tree.left) + countLeafNodes(tree.right);
}

在上述代码中，我们采用递归方式遍历二叉树。如果节点为空，说明该子树中没有节点，返回零；否则，如果该节点没有左右子树，说明该节点为叶子节点，返回1；最后，递归遍历左右子树，统计叶子节点个数并返回。

其次，要求二叉树结点总数。同样采用递归遍历的方式，统计每个节点出现的次数。以下是求二叉树节点总数的代码：

int countNodes(BinaryTree tree) {
    if (tree == null) {
        return 0;
    }
    return countNodes(tree.left) + countNodes(tree.right) + 1;
}

在上述代码中，我们采用递归方式遍历二叉树。如果节点为空，说明该子树中没有节点，返回零；否则，递归遍历左右子树，并将其节点总数相加，再加上当前节点，即为整棵二叉树的节点总数。

最后，要求二叉树的深度。在二叉树中，深度也称为高度，是从根节点到最底层节点的最长路径的长度。我们同样采用递归的方式遍历二叉树，求出左右子树的深度，然后取最大值加1即可。以下是求二叉树深度的代码：

int getTreeDepth(BinaryTree tree) {
    if (tree == null) {
        return 0;
    }
    int leftDepth = getTreeDepth(tree.left);
    int rightDepth = getTreeDepth(tree.right);
    return Math.max(leftDepth, rightDepth) + 1;
}

在上述代码中，我们采用递归方式遍历二叉树。如果节点为空，说明该子树中没有节点，返回零；否则，递归计算左右子树的深度，取最大值并加上1，即为该节点所在子树的深度。整棵二叉树的深度即为根节点的深度。

一、问题描述 已知一棵二叉树,求该二叉树的叶结点的个数 、基本要求 (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;
}