二叉树 由中序遍历和前序遍历推后序遍历

根据后序遍历’=‘左子树的后序遍历’+‘右子树的后序遍历’+‘根节点递归求解即可

char pre[maxn], in[maxn], post[maxn]; void Post(char* _pre, char* _in, int _len, int _root) { if (_len <= 0) return; int i = 0; while (_in[i] != _pre[0]) ++i; Post(_pre + 1, _in, i, _root - (_len - i - 1) - 1); Post(_pre + i + 1, _in + i + 1, _len - i - 1, _root - 1); post[_root] = _pre[0]; } int main() { //std::ios::sync_with_stdio(0); //std::cin.tie(0); #ifdef NIGHT_13 freopen("in.txt", "r", stdin); //freopen("myout.txt", "w", stdout); #endif scanf("%s%s", pre, in); int len = strlen(in); Post(pre, in, len, len - 1); printf("%s\n", post); return 0; }