给出递归计算二叉树中只有右孩子的结点的数量的算法
时间: 2023-11-14 09:07:17 浏览: 100
可以使用递归的方式来计算二叉树中只有右孩子的结点数量:
1. 如果当前节点为 NULL,返回 0。
2. 如果当前节点只有右孩子,返回 1 + 递归计算右孩子的只有右孩子的结点数量。
3. 如果当前节点有左孩子,返回递归计算左孩子的只有右孩子的结点数量 + 递归计算右孩子的只有右孩子的结点数量。
以下是对应的 C++ 代码实现:
```c++
int countRightOnly(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right != NULL) {
return 1 + countRightOnly(root->right);
}
return countRightOnly(root->left) + countRightOnly(root->right);
}
```
这个算法的时间复杂度是 O(n),其中 n 是二叉树中结点的数量,因为需要遍历每个节点一次。
相关问题
C语言递归计算二叉树的深度和叶子结点的个数算法分析
递归计算二叉树的深度和叶子结点的个数是二叉树常见的算法之一。
算法思路如下:
1. 判断当前节点是否为空,如果为空,则返回0
2. 递归计算左子树的深度和叶子结点个数
3. 递归计算右子树的深度和叶子结点个数
4. 返回左右子树深度较大值加1,叶子结点个数相加的结果
具体的C语言代码实现如下:
```
#include <stdio.h>
#include <stdlib.h>
// 二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 计算二叉树深度和叶子结点个数
void calDepthAndLeaf(TreeNode* root, int* depth, int* leaf) {
if (root == NULL) {
*depth = 0;
*leaf = 0;
return;
}
int leftDepth, leftLeaf, rightDepth, rightLeaf;
calDepthAndLeaf(root->left, &leftDepth, &leftLeaf);
calDepthAndLeaf(root->right, &rightDepth, &rightLeaf);
*depth = (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
*leaf = leftLeaf + rightLeaf;
if (root->left == NULL && root->right == NULL) {
*leaf += 1;
}
}
int main() {
// 构造一棵二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
int depth, leaf;
calDepthAndLeaf(root, &depth, &leaf);
printf("二叉树的深度为:%d\n", depth);
printf("二叉树的叶子结点个数为:%d\n", leaf);
return 0;
}
```
以上代码中,我们测试了一棵如下的二叉树:
```
1
/ \
2 3
/ \
4 5
```
运行结果如下:
```
二叉树的深度为:3
二叉树的叶子结点个数为:3
```
可以看出,我们的代码计算出了该二叉树的深度和叶子结点个数。
递归计算二叉树的深度和叶子结点的个数算法分析
计算二叉树的深度和叶子节点个数,可以使用递归算法。首先,对于叶子节点,其深度为1,叶子节点数为1;对于非叶子节点,其深度为左右子树深度的最大值加1,叶子节点数为左右子树叶子节点数之和。
具体算法如下:
1. 如果二叉树为空,则深度为0,叶子节点为0。
2. 如果二叉树只有一个根节点,则深度为1,叶子节点为1。
3. 如果二叉树有左子树,递归计算左子树的深度和叶子节点个数。
4. 如果二叉树有右子树,递归计算右子树的深度和叶子节点个数。
5. 对于非叶子节点,深度为左右子树深度的最大值加1,叶子节点数为左右子树叶子节点数之和。
6. 返回深度和叶子节点数。
以下是 Python 代码实现:
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def depthAndLeafCount(root):
if root is None:
return 0, 0
if root.left is None and root.right is None:
return 1, 1
left_depth, left_leaf_count = depthAndLeafCount(root.left)
right_depth, right_leaf_count = depthAndLeafCount(root.right)
depth = max(left_depth, right_depth) + 1
leaf_count = left_leaf_count + right_leaf_count
return depth, leaf_count
```
其中depthAndLeafCount函数返回一个元组,第一个元素为二叉树的深度,第二个元素为二叉树的叶子节点数。