按先序遍历序列建立一个二叉树的二叉链表,统计二叉树中叶子结点个数和二叉树的深度。
时间: 2023-11-13 13:04:46 浏览: 109
二叉树的遍历与求深度以及结点数
5星 · 资源好评率100%
我们可以使用递归来实现按先序遍历序列建立一个二叉树的二叉链表。首先,定义二叉树的结构体:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
然后,根据先序遍历序列建立二叉树的函数如下:
```c++
TreeNode* buildTree(vector<int>& preorder, int& index) {
if (index >= preorder.size() || preorder[index] == -1) {
return NULL;
}
TreeNode* root = new TreeNode(preorder[index]);
index++;
root->left = buildTree(preorder, index);
index++;
root->right = buildTree(preorder, index);
return root;
}
```
其中,-1 表示空节点。我们使用一个全局变量 index 来记录当前遍历到的位置。
接下来,我们可以使用递归来统计二叉树中叶子结点个数和二叉树的深度。具体实现如下:
```c++
void countLeafAndDepth(TreeNode* root, int& leafCount, int& depth, int curDepth) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
leafCount++;
depth = max(depth, curDepth);
}
countLeafAndDepth(root->left, leafCount, depth, curDepth + 1);
countLeafAndDepth(root->right, leafCount, depth, curDepth + 1);
}
```
其中,leafCount 和 depth 分别表示叶子结点个数和二叉树的深度,curDepth 表示当前遍历到的深度。如果当前节点是叶子结点,就将 leafCount 加一,并更新深度 depth。然后,递归遍历左子树和右子树。
完整代码如下:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<int>& preorder, int& index) {
if (index >= preorder.size() || preorder[index] == -1) {
return NULL;
}
TreeNode* root = new TreeNode(preorder[index]);
index++;
root->left = buildTree(preorder, index);
index++;
root->right = buildTree(preorder, index);
return root;
}
void countLeafAndDepth(TreeNode* root, int& leafCount, int& depth, int curDepth) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
leafCount++;
depth = max(depth, curDepth);
}
countLeafAndDepth(root->left, leafCount, depth, curDepth + 1);
countLeafAndDepth(root->right, leafCount, depth, curDepth + 1);
}
int main() {
vector<int> preorder = {1, 2, -1, -1, 3, 4, -1, -1, 5, -1, -1};
int index = 0;
TreeNode* root = buildTree(preorder, index);
int leafCount = 0, depth = 0;
countLeafAndDepth(root, leafCount, depth, 1);
cout << "Leaf count: " << leafCount << endl;
cout << "Depth: " << depth << endl;
return 0;
}
```
阅读全文