Untitled
unknown
plain_text
8 days ago
1.7 kB
3
Indexable
Never
#include <iostream> #include <vector> #include <stack> using namespace std; // Definition for a binary tree node. struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // Helper function to insert a new node into the BST TreeNode* insertIntoBST(TreeNode* root, int val) { if (!root) return new TreeNode(val); if (val < root->val) { root->left = insertIntoBST(root->left, val); } else { root->right = insertIntoBST(root->right, val); } return root; } // Function to reconstruct BST from preorder traversal TreeNode* bstFromPreorder(const vector<int>& preorder) { if (preorder.empty()) return nullptr; TreeNode* root = nullptr; for (int value : preorder) { root = insertIntoBST(root, value); } return root; } // Helper function for postorder traversal void postorderTraversal(TreeNode* root, vector<int>& result) { if (root) { postorderTraversal(root->left, result); postorderTraversal(root->right, result); result.push_back(root->val); } } // Function to print vector contents void printVector(const vector<int>& v) { for (size_t i = 0; i < v.size(); ++i) { if (i > 0) cout << " "; cout << v[i]; } cout << endl; } int main() { int n; cin >> n; vector<int> preorder(n); for (int i = 0; i < n; ++i) { cin >> preorder[i]; } // Reconstruct BST TreeNode* root = bstFromPreorder(preorder); // Perform postorder traversal vector<int> postorder; postorderTraversal(root, postorder); // Output postorder traversal printVector(postorder); return 0; }
Leave a Comment