前序遍历建立一颗二叉树
时间: 2023-06-11 19:09:42 浏览: 51
前序遍历建立一颗二叉树的步骤如下:
1. 如果前序遍历序列为空,则返回空树。
2. 取出前序遍历序列的第一个元素作为根节点。
3. 根据根节点,在前序遍历序列中找到左子树和右子树的分界点。
4. 递归地对左子树和右子树进行建立,分别作为根节点的左子树和右子树。
5. 返回根节点。
具体实现可以参考下面的代码(假设前序遍历序列存储在数组 pre 中,数组长度为 n):
```
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& pre, int& index, int left, int right) {
if (index >= pre.size() || left > right) {
return nullptr;
}
int val = pre[index++];
TreeNode* root = new TreeNode(val);
int pos = left;
while (pos <= right && pre[pos] != val) {
pos++;
}
root->left = buildTree(pre, index, left, pos - 1);
root->right = buildTree(pre, index, pos + 1, right);
return root;
}
TreeNode* buildTree(vector<int>& pre) {
int index = 0;
return buildTree(pre, index, 0, pre.size() - 1);
}
```
调用 buildTree(pre) 即可建立一颗二叉树。