一本通-1339：【例3-4】求后序遍历

【题目描述】 输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。

【输入】 共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。树的结点一律用小写字母表示。

【输出】 一行，表示树的后序遍历序列。

【输入样例】 abdec dbeac

【输出样例】 debca

---

#include <bits/stdc++.h>

using namespace std;

string preorder, inorder;

struct TreeNode
{
    char ch;
    TreeNode *left, *right;
    TreeNode(char x): ch(x), left(NULL), right(NULL) {}
};

TreeNode *treeBuild(int in_start, int in_end, int pre_start, int pre_end)
{
    if (in_start == in_end || pre_start == pre_end) return NULL;

    TreeNode *root = new TreeNode(preorder[pre_start]); //建立根节点

    int inRootPos = inorder.find(preorder[pre_start]);
    int leftSize = inRootPos - in_start;

    root -> left = treeBuild(in_start, inRootPos, pre_start + 1, pre_start + 1 + leftSize);
    root -> right = treeBuild(inRootPos + 1, in_end, pre_start + 1 + leftSize, pre_end);

    return root;
}

void postorderTraversal(TreeNode *root)
{
    if (!root) return;
    postorderTraversal(root -> left);
    postorderTraversal(root -> right);
    cout << root -> ch;
}

void makeEmpty(TreeNode *&root)
{
    if (root) {
        makeEmpty(root -> left);
        makeEmpty(root -> right);
        delete root;
        root = NULL;
    }
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> preorder >> inorder;

    TreeNode *root = treeBuild(0, inorder.size(), 0, preorder.size());
    postorderTraversal(root);
    makeEmpty(root);

    return 0;
}