tree_construct.cpp

// 由前序遍歷和中序遍歷構造二叉樹

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Core functions: use preorder and inorder to construct the tree
// preorder: root, left, right
// inorder: left, root, right
TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                vector<int>& inorder, int inStart, int inEnd) {
    
    // base case: if the preorder or inorder is empty, return nullptr
    if (preStart > preEnd) return nullptr;

    // Step 1: the first element of preorder is the root
    int rootVal = preorder[(size_t)preStart];
    TreeNode* root = new TreeNode(rootVal);

    // Step 2: find the root in the inorder
    int rootIdx = inStart;
    while (inorder[(size_t)rootIdx] != rootVal) rootIdx++;

    // Step 3: count the number of nodes in the left subtree
    int leftSize = rootIdx - inStart;

    // Step 4: construct the left subtree
    // - preorder: [preStart + 1, preStart + leftSize]
    // - inorder: [inStart, rootIdx -1]
    root->left = build(preorder, preStart + 1, preStart + leftSize,
                       inorder, inStart, rootIdx - 1);

    // Step 5: construct the right subtree
    // - preorder: [preStart+leftSize+1, preEnd]
    // - inorder: [rootIdx+1, inEnd]
    root->right = build(preorder, preStart + leftSize +1, preEnd,
                        inorder, rootIdx + 1, inEnd);

    return root;
}

// postorder traversal to print the tree
void postorder(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    postorder(root->left, result);
    postorder(root->right, result);
    result.push_back(root->val);
}

// Helper function to free memory
void freeTree(TreeNode* node) {
    if (node == nullptr) return;
    freeTree(node->left);
    freeTree(node->right);
    delete node;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<int> preorder((size_t)N), inorder((size_t)N);

        for (size_t i = 0; i < (size_t)N; i++) cin >> preorder[i];
        for (size_t i = 0; i < (size_t)N; i++) cin >> inorder[i];

        // construct the tree
        TreeNode* root = build(preorder, 0, N-1, inorder, 0, N-1);

        // Get the postorder traversal
        vector<int> result;
        postorder(root, result);

        // print the result
        for (size_t i = 0; i < (size_t)N; i++) cout << result[i] << " ";
        cout << endl;

        // free the tree
        freeTree(root);
    }
    return 0;
}