#include <iostream>
#include <vector>
using namespace std;
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder);
TreeNode* buildTreeHelper(vector<int>& preorder, vector<int>& inorder, int preStart, int preEnd, int inStart, int inEnd);
void printPostorder(TreeNode* node);
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);
cout << "Postorder Traversal: ";
printPostorder(root);
return 0;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTreeHelper(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}
TreeNode* buildTreeHelper(vector<int>& preorder, vector<int>& inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return nullptr;
}
int rootValue = preorder[preStart];
TreeNode* root = new TreeNode(rootValue);
int rootIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootValue) {
rootIndex = i;
break;
}
}
int leftSubtreeSize = rootIndex - inStart;
root->left = buildTreeHelper(preorder, inorder, preStart + 1, preStart + leftSubtreeSize, inStart, rootIndex - 1);
root->right = buildTreeHelper(preorder, inorder, preStart + leftSubtreeSize + 1, preEnd, rootIndex + 1, inEnd);
return root;
}
void printPostorder(TreeNode* node) {
if (node == nullptr) {
return;
}
printPostorder(node->left);
printPostorder(node->right);
cout << node->val << " ";
}