给你一颗二叉树,请你求出该二叉树的结点总数。用C语言写出来
时间: 2024-01-23 11:07:10 浏览: 33
好的,下面给出用 C 语言实现的递归算法:
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int countNodes(struct TreeNode* root){
if (!root) {
return 0;
}
int left_height = getHeight(root->left);
int right_height = getHeight(root->right);
if (left_height == right_height) {
// 左子树是一棵满二叉树,右子树是一棵普通二叉树
return (1 << left_height) + countNodes(root->right);
} else {
// 右子树是一棵满二叉树,左子树是一棵普通二叉树
return (1 << right_height) + countNodes(root->left);
}
}
int getHeight(struct TreeNode* node) {
int height = 0;
while (node) {
height++;
node = node->left;
}
return height;
}
```
这个算法的时间复杂度同样是 $O(\log^2 n)$,其中 $n$ 是二叉树的节点数。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)