用递归算法统计二叉树的叶结点个数
时间: 2024-01-22 12:19:50 浏览: 32
递归算法是一种自己调用自己的算法,对于统计二叉树的叶结点个数,可以使用递归算法来实现。具体步骤如下:
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` 三个成员变量,分别表示节点的值、左子节点和右子节点。
相关问题
非递归算法求二叉树的叶结点个数C++
可以使用迭代法(非递归算法)来求解二叉树的叶结点个数,具体思路如下:
1.定义一个计数器 count,初始化为0。
2.使用栈来遍历二叉树。首先将根节点入栈。
3.进入循环,当栈不为空时执行以下操作:
- 弹出栈顶元素,如果该元素为叶结点,则将 count 加1。
- 如果该元素有右子树,则将右子树入栈。
- 如果该元素有左子树,则将左子树入栈。
4.遍历结束后,返回 count 值即可。
下面是C++代码实现:
```c++
int countLeaves(TreeNode* root) {
if (!root) {
return 0;
}
int count = 0;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
if (!node->left && !node->right) {
count++;
}
if (node->right) {
st.push(node->right);
}
if (node->left) {
st.push(node->left);
}
}
return count;
}
```
其中,TreeNode 表示二叉树的节点。
用非递归算法求二叉树的叶结点个数c
可以使用迭代法(非递归)实现二叉树的叶子节点个数。具体步骤如下:
1. 定义一个栈来存储节点指针。
2. 从根节点开始,将根节点指针入栈。
3. 循环遍历栈中的节点指针,如果该节点是叶子节点,则叶子节点个数加1;否则,将该节点的左右子节点指针分别入栈。
4. 直到栈为空,遍历结束,返回叶子节点个数。
以下是C++代码实现:
```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` 分别表示左右子节点的指针。