Untitled

mail@pastecode.io avatar
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