根据二叉树的后序和中序遍历输出先序遍历

7-8 根据后序和中序遍历输出先序遍历 (20分)

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

输入格式:
第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式: 在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例:
Preorder: 4 1 3 2 6 5 7

思路
因为后续遍历的最后一个数是二叉树的根节点，所以我们可以通过分岔递归（这个词自己编的）每次打印后续遍历的最后一个数，不断的把树的第一个节点打印，把先序遍历完成。

在中序遍历的数组中，根结点左边的节点数就是左子树的节点总数，根结点右边的节点数是右子树的节点总数，由此我们可以根据根结点坐标间的一些信息把这棵树分为左右子树，并得到它们的后续遍历和中序遍历，递归调用函数。递归的回溯条件是坐标起点值大于坐标终点值。

其中，我们可以通过一个哈希表把中序遍历的每个数的坐标记录下来，每次根据后续遍历的最后一个数的值找到其对应中序遍历的坐标，我们要让递归顺利进行，就需要知道后序遍历和中序遍历的起始坐标和终点坐标，通过坐标求得左右子树的节点个数继续安排下次递归的后序遍历和中序遍历的起始坐标和终点坐标
代码

#include <iostream>
#include <map>
using namespace std;

int postOrder[30], inOrder[30];//不用全局变量也可带入函数形参
map<int, int> Index;//用unordered_map更快

void printPreOrder(int postStart,int postEnd,int inStart, int inEnd) {
    if (postStart > postEnd)
        return;
    printf(" %d", postOrder[postEnd]);
    int index = Index[postOrder[postEnd]]; //中序遍历中树第一个节点的坐标
    int leftNodes = index - inStart, rightNodes = inEnd - index;
    printPreOrder(postStart, postEnd - rightNodes - 1, inStart, index - 1);
    printPreOrder(postEnd - rightNodes, postEnd - 1, index + 1, inEnd);
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> postOrder[i];
    for (int i = 0; i < n; i++) {
        cin >> inOrder[i];
        Index[inOrder[i]] = i;
    }
    printf("Preorder:");
    printPreOrder(0, n - 1, 0, n - 1);
}