ACM----已知前序遍历序列和后序遍历序列求后序遍历序列

很是激动，离开ACM一年后还能找回当时ac时激动的感觉。虽然挺简单的一题，在苦思冥想之后想到左右子树分治采用递归解法。一次Compilation Error后就ac了。就算是重启刷题的开门红吧。

这是原题：ZOJ-1944

答案：

//
// Created by PC on 2019/2/28.
// 通过前序遍历和中序遍历字母树获得的字符串获取后序遍历的字符串！
// 深思熟虑后觉得应该用递归
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
// DBACEGF ABCDEFG
stack<char> post;

//先找出每个子树的根节点，然后获取其左子树和右子树
void separateSubTree(char preOrder[], char inOrder[]) {

    // 这是递归的判断
    if(strlen(preOrder) == 0) {
        return;
    }
    post.push(preOrder[0]);

    // 根节点就是preOrder的第一个字母，根据根节点从inOrder中分成左右子树
    // 这里的教训惨重啊，字符数组不赋初值，就会被自动赋一些乱七八糟的值，影响后面的结果！
    char inLeft[20] = "", inRight[20] = "";
    char preLeft[20] = "", preRight[20] = "";
    char* middle = strchr(inOrder, preOrder[0]);

    // 左子树
    memcpy(inLeft, inOrder, middle - inOrder);

    // 右子树
    memcpy(inRight, middle + 1, strlen(inOrder) - 1 - (middle - inOrder));

    //前面都是中序遍历的左右子树！下面获取前序遍历的左右子树，获取后直接再调用本方法获取就行了
    // 左子树
    memcpy(preLeft, preOrder + 1, strlen(inLeft));

    // 右子树
    memcpy(preRight, preOrder + strlen(inLeft) + 1, strlen(inRight));

    separateSubTree(preRight, inRight);
    separateSubTree(preLeft, inLeft);
}

int main() {
    char preOrder[27], inOrder[27];
    while (scanf("%s %s", preOrder, inOrder) != EOF) {
        // int postOrder[27];
        separateSubTree(preOrder, inOrder);
        //cout << post.size() << endl;
        while (!post.empty()) {
            cout << post.top();
            post.pop();
        }
        cout << endl;
    }
    return 0;
}