根据后序和中序遍历输出先序遍历
时间: 2023-11-17 18:07:55 浏览: 54
根据后序和中序遍历输出先序遍历的过程如下:
1. 首先根据后序遍历确定根节点。
2. 在中序遍历中找到根节点对应的下标。
3. 计算分割区间的左右位置。
4. 递归处理左右子树。
具体实现可以参考以下代码:
```
void post_in_to_pre(int post[], int in[], int n, int& pre_index, int in_left, int in_right, vector<int>& pre) {
if (in_left > in_right) {
return;
}
int root = post[pre_index];
pre_index--;
int in_index = in_left;
while (in_index <= in_right && in[in_index] != root) {
in_index++;
}
pre.push_back(root);
post_in_to_pre(post, in, n, pre_index, in_index + 1, in_right, pre);
post_in_to_pre(post, in, n, pre_index, in_left, in_index - 1, pre);
}
vector<int> get_preorder(int post[], int in[], int n) {
vector<int> pre;
int pre_index = n - 1;
post_in_to_pre(post, in, n, pre_index, 0, n - 1, pre);
return pre;
}
```
其中,post_in_to_pre函数用于递归处理左右子树,get_preorder函数用于返回先序遍历结果。