给一颗满二叉树的先序便利。然后求出它的中序遍历。
时间: 2023-04-04 13:01:13 浏览: 56
可以使用递归的方式来求解。先序遍历的第一个节点一定是根节点,然后将树分为左子树和右子树,再分别对左右子树进行递归。中序遍历的顺序是先遍历左子树,然后遍历根节点,最后遍历右子树。
具体步骤如下:
1. 如果树为空,返回空列表。
2. 取先序遍历的第一个节点作为根节点。
3. 找到根节点在中序遍历中的位置,将中序遍历分为左子树和右子树。
4. 对左子树进行递归,得到左子树的中序遍历。
5. 对右子树进行递归,得到右子树的中序遍历。
6. 将左子树的中序遍历、根节点、右子树的中序遍历依次加入结果列表中。
7. 返回结果列表。
代码如下:
```
#include <iostream>
#include <vector>
using namespace std;
vector<int> inorderTraversal(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty()) {
return {};
}
int root = preorder[];
vector<int> left_preorder, left_inorder, right_preorder, right_inorder;
int i = ;
while (inorder[i] != root) {
left_inorder.push_back(inorder[i]);
i++;
}
i++;
while (i < inorder.size()) {
right_inorder.push_back(inorder[i]);
i++;
}
for (int j = 1; j < preorder.size(); j++) {
if (j <= left_inorder.size()) {
left_preorder.push_back(preorder[j]);
} else {
right_preorder.push_back(preorder[j]);
}
}
vector<int> left = inorderTraversal(left_preorder, left_inorder);
vector<int> right = inorderTraversal(right_preorder, right_inorder);
left.push_back(root);
left.insert(left.end(), right.begin(), right.end());
return left;
}
int main() {
vector<int> preorder = {1, 2, 4, 5, 3, 6, 7};
vector<int> inorder = {4, 2, 5, 1, 6, 3, 7};
vector<int> result = inorderTraversal(preorder, inorder);
for (int i = ; i < result.size(); i++) {
cout << result[i] << " ";
}
cout << endl;
return ;
}
```
输出结果为:4 2 5 1 6 3 7。