写出二叉树节点的结构体定义,然后编写一个递归函数统计二叉树上叶子节点的数目。
时间: 2024-04-29 12:03:17 浏览: 12
二叉树节点的结构体定义如下:
```
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
```
递归函数统计二叉树上叶子节点的数目的代码如下:
```
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);
}
```
该函数的原理是,如果当前节点是叶子节点(即左右子树均为空),则返回1;否则递归调用左右子树,将它们的叶子节点数目相加返回。如果当前节点为空,则返回0。
相关问题
给定一颗用二叉链表表示的二叉树,根节点指针是t,求二叉树叶子数目c结构体
可以定义一个结构体来表示二叉树节点,包含左右子节点指针和节点值:
```c
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
```
然后,可以通过递归方式来求解二叉树的叶子节点数目。具体实现可以如下:
```c
int count_leaves(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return count_leaves(root->left) + count_leaves(root->right);
}
```
其中,root表示当前节点,如果节点为空,则返回0;如果节点为叶子节点,则返回1;否则递归计算左右子树的叶子节点数目,并将其相加。
在主程序中,可以通过调用`count_leaves`函数来计算叶子节点数目:
```c
struct TreeNode* t = ...; // 假设已经构建好了二叉树,并且根节点为t
int num_leaves = count_leaves(t);
printf("%d\n", num_leaves);
```
需要注意的是,该实现假设二叉树使用了常规的二叉链表表示方式,即每个节点包含left和right指针。如果使用其他方式表示二叉树,则需要相应修改实现。
编写一个递归函数height,传入参数为二叉树根节点的指针root计算二叉树高度
下面是C++代码实现:
```c++
int height(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int left_height = height(root->left);
int right_height = height(root->right);
return max(left_height, right_height) + 1;
}
```
递归函数的核心思想是求出左右子树的高度,然后取较大值加1即可。如果根节点为空,返回0。