c++根据前序遍历和中序遍历够建二叉树并输出后序遍历
时间: 2023-12-14 22:31:18 浏览: 127
数据结构C++二叉树的先序遍历、中序遍历和后序遍历实现
5星 · 资源好评率100%
根据前序遍历和中序遍历构建二叉树的步骤如下:
1. 前序遍历的第一个节点为根节点,找到该节点在中序遍历中的位置,将中序遍历分为左子树和右子树两部分。
2. 根据左子树和右子树的节点数量,将前序遍历分为左子树和右子树两部分。
3. 递归构建左子树和右子树。
下面是根据提供的前序遍历和中序遍历构建二叉树并输出后序遍历的代码:
```c++
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> inorder_map;
for (int i = 0; i < inorder.size(); i++) {
inorder_map[inorder[i]] = i;
}
return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inorder_map);
}
TreeNode* buildTreeHelper(vector<int>& preorder, int pre_start, int pre_end, vector<int>& inorder, int in_start, int in_end, unordered_map<int, int>& inorder_map) {
if (pre_start > pre_end || in_start > in_end) {
return nullptr;
}
int root_val = preorder[pre_start];
int root_index = inorder_map[root_val];
int left_size = root_index - in_start;
TreeNode* root = new TreeNode(root_val);
root->left = buildTreeHelper(preorder, pre_start + 1, pre_start + left_size, inorder, in_start, root_index - 1, inorder_map);
root->right = buildTreeHelper(preorder, pre_start + left_size + 1, pre_end, inorder, root_index + 1, in_end, inorder_map);
return root;
}
void postorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
int main() {
vector<int> preorder = {1, 2, 4, 5, 3, 6, 7};
vector<int> inorder = {4, 2, 5, 1, 6, 3, 7};
TreeNode* root = buildTree(preorder, inorder);
postorderTraversal(root);
return 0;
}
```
输出结果为:4 5 2 6 7 3 1
阅读全文