编写完整代码实现如下功能 1、输入字符串序列,进行二叉树的构建; 2、基于构建的的二叉树结构计算其深度; 3、基于构建的二叉树结构计算其叶子结点个数。
时间: 2024-05-01 22:17:44 浏览: 12
好的,您的要求我已经收到了。以下是代码实现:
```
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
//定义二叉树结点
struct TreeNode {
int val; //结点的值
TreeNode* left; //左子树
TreeNode* right; //右子树
TreeNode(int x): val(x), left(NULL), right(NULL) {}
};
//构建二叉树
TreeNode* buildBinaryTree(vector<int>& nums) {
if(nums.empty()) return NULL; //序列为空返回空指针
queue<TreeNode*> nodeQueue; //记录每一层的结点
TreeNode* root = new TreeNode(nums[0]); //根结点
nodeQueue.push(root);
int i = 1;
while(!nodeQueue.empty() && i < nums.size()) { //循环处理每一层的结点
TreeNode* node = nodeQueue.front();
nodeQueue.pop();
//左子树
if(i < nums.size() && nums[i] != -1) {
node->left = new TreeNode(nums[i]);
nodeQueue.push(node->left);
}
i++;
//右子树
if(i < nums.size() && nums[i] != -1) {
node->right = new TreeNode(nums[i]);
nodeQueue.push(node->right);
}
i++;
}
return root;
}
//计算二叉树的深度
int binaryTreeDepth(TreeNode* root) {
if(root == NULL) return 0;
int leftDepth = binaryTreeDepth(root->left); //计算左子树深度
int rightDepth = binaryTreeDepth(root->right); //计算右子树深度
return max(leftDepth, rightDepth) + 1; //返回子树中深度较大的值加1
}
//计算二叉树叶子结点的个数
int binaryTreeLeaves(TreeNode* root) {
if(root == NULL) return 0;
if(root->left == NULL && root->right == NULL) return 1; //叶子结点
int leftLeaves = binaryTreeLeaves(root->left); //计算左子树叶子结点个数
int rightLeaves = binaryTreeLeaves(root->right); //计算右子树叶子结点个数
return leftLeaves + rightLeaves; //返回叶子结点个数
}
int main() {
//输入字符串序列
vector<int> nums = {1,2,3,4,5,6,7,-1,-1,8,-1,-1,-1,-1,-1};
//构建二叉树
TreeNode* root = buildBinaryTree(nums);
//计算二叉树的深度
int depth = binaryTreeDepth(root);
cout << "depth = " << depth << endl;
//计算二叉树叶子结点的个数
int leaves = binaryTreeLeaves(root);
cout << "leaves = " << leaves << endl;
return 0;
}
```
以上代码可以实现输入一个字符串序列,通过构建二叉树可以计算其深度和叶子结点个数。其中,-1 表示空结点。您可以根据实际需要修改输入的字符串序列。