请用C++实现:给出一棵二叉树的前序遍历 (preorder) 和中序遍历 (inorder),求它的后序遍历 (postorder)。
时间: 2024-05-09 22:15:59 浏览: 86
数据结构C++二叉树的先序遍历、中序遍历和后序遍历实现
5星 · 资源好评率100%
这道题可以用递归的方式解决,具体实现如下:
```c++
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty() || inorder.empty()) {
return NULL;
}
int rootVal = preorder[0];
TreeNode* root = new TreeNode(rootVal);
int rootIndex = 0;
for (int i = 0; i < inorder.size(); i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + rootIndex + 1);
vector<int> rightPreorder(preorder.begin() + rootIndex + 1, preorder.end());
vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIndex);
vector<int> rightInorder(inorder.begin() + rootIndex + 1, inorder.end());
root->left = buildTree(leftPreorder, leftInorder);
root->right = buildTree(rightPreorder, rightInorder);
return root;
}
void postorderTraversal(TreeNode* root, vector<int>& postorder) {
if (root == NULL) {
return;
}
postorderTraversal(root->left, postorder);
postorderTraversal(root->right, postorder);
postorder.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> postorder;
postorderTraversal(root, postorder);
return postorder;
}
int main() {
vector<int> preorder = { 1,2,4,5,3,6 };
vector<int> inorder = { 4,2,5,1,3,6 };
TreeNode* root = buildTree(preorder, inorder);
vector<int> postorder = postorderTraversal(root);
for (int i = 0; i < postorder.size(); i++) {
cout << postorder[i] << " ";
}
cout << endl;
return 0;
}
```
其中,`buildTree` 函数用来构建二叉树,`postorderTraversal` 函数用来进行后序遍历。具体思路是先找到前序遍历序列中的根节点,然后在中序遍历序列中找到根节点的位置,根节点左边的部分就是左子树的中序遍历序列,根节点右边的部分就是右子树的中序遍历序列。然后根据左右子树的中序遍历序列长度可以在前序遍历序列中分离出左右子树的前序遍历序列。然后递归构建左右子树即可。最后进行后序遍历即可得到答案。
阅读全文