写一个利用先序序列生成二叉树的函数
时间: 2024-04-30 18:22:02 浏览: 11
以下是一个利用先序序列生成二叉树的函数实现(C++):
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& preorder, int& index, int limit) {
if (index >= preorder.size() || preorder[index] > limit) {
return nullptr;
}
int val = preorder[index++];
TreeNode* node = new TreeNode(val);
node->left = buildTree(preorder, index, val);
node->right = buildTree(preorder, index, limit);
return node;
}
TreeNode* buildTree(vector<int>& preorder) {
int index = 0;
return buildTree(preorder, index, INT_MAX);
}
```
该函数的核心思想是利用先序遍历中的顺序,找到当前节点的值,并根据其在先序序列中的位置,判断其左右子树的范围,并递归构建子树。具体来说,构建二叉树的过程如下:
1. 如果先序序列为空或当前节点的值大于上限,则返回空节点。
2. 取出先序序列中的第一个元素作为当前节点的值。
3. 构建当前节点,并递归构建其左子树和右子树,左子树的上限为当前节点的值,右子树的上限为上限值。
4. 返回当前节点。
函数最后返回根节点,即构建完成的二叉树。