POJ2255

二叉树基础题目：已知前序遍历和中序遍历，求后序遍历
原理链接：

思路：利用中序和前序重建二叉树，然后后序遍历输出。

代码：

#include <iostream>
#include <string>

using namespace std;

struct Node {
    char val;
    Node *left;
    Node *right;

    Node(char c='*'): val(c), left(NULL), right(NULL) {}
};

class BinaryTree {
    public:
        BinaryTree(): root(NULL) {}
        void run() {
            while (cin>>preOrder>>inOrder) {
                buildTree();
                postOrder();
            }
        }

    private:
        void buildTree() {
            root = buildTree(0, preOrder.size()-1, 0, inOrder.size()-1);
        }

        Node* buildTree(int preBegin, int preEnd, int inBegin, int inEnd) {
            if (preBegin > preEnd)
                return NULL;
            int mid;
            for (mid = inBegin; mid <= inEnd; mid++)
                if (preOrder[preBegin] == inOrder[mid])
                    break;
            Node *tree = new Node(inOrder[mid]);
            tree->left = buildTree(preBegin+1, preBegin+mid-inBegin, inBegin, mid-1);
            tree->right = buildTree(preBegin+mid-inBegin+1, preEnd, mid+1, inEnd);

            return tree;
        }

        void postOrder() {
            postOrder(root);
            root = NULL;
            cout << endl;
        }

        void postOrder(Node *tree) {
            if (tree == NULL)
                return;
            postOrder(tree->left);
            postOrder(tree->right);
            cout << tree->val;
            delete tree;
        }

        Node *root;
        string preOrder;
        string inOrder;
};

int main() {
    BinaryTree btree;
    btree.run();

    return 0;
}