剑指offer中题目：http://ac.jobdu.com/problem.php?pid=1385

题目描写叙述：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。如果输入的前序遍历和中序遍历的结果中都不含反复的数字。

比如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并输出它的后序遍历序列。

输入：

输入可能包括多个測试例子，对于每一个測试案例，

输入的第一行为一个整数n(1<=n<=1000)：代表二叉树的节点个数。

输入的第二行包含n个整数(当中每一个元素a的范围为(1<=a<=1000))：代表二叉树的前序遍历序列。

输入的第三行包含n个整数(当中每一个元素a的范围为(1<=a<=1000))：代表二叉树的中序遍历序列。

输出：

相应每一个測试案例，输出一行：

假设题目中所给的前序和中序遍历序列能构成一棵二叉树。则输出n个整数，代表二叉树的后序遍历序列。每一个元素后面都有空格。

假设题目中所给的前序和中序遍历序列不能构成一棵二叉树。则输出”No”。

例子输入：

8

1 2 4 7 3 5 6 8 

4 7 2 1 5 3 8 6

8

1 2 4 7 3 5 6 8

4 1 2 7 5 3 8 6

例子输出：

7 4 2 5 8 6 3 1 No

这个题用递归来重建二叉树，详细代码例如以下：

#include <stdio.h>

#include <stdlib.h>

#define SIZE 1001

typedef struct STreeNode

{

    int data;

    struct STreeNode *left;

    struct STreeNode *right;

}STreeNode;

int ArrPre[SIZE];

int ArrMid[SIZE];

int CanBuild;

int getMidPos(int vKey, int vStart, int vEnd)

{

    int i;

    for (i = vStart; i < vEnd; ++i)

    {

        if (ArrMid[i] == vKey) return i;

    }

    return -1;

}

void createNode(STreeNode **vNode, int vData)

{

    *vNode = (STreeNode *)malloc(sizeof(STreeNode));

    (*vNode)->data  = vData;

    (*vNode)->left  = NULL;

    (*vNode)->right = NULL;

}

void destroyNode(STreeNode **vNode)

{

    (*vNode)->left  = NULL;

    (*vNode)->right = NULL;

    free(*vNode);

}

void createBinaryTree(STreeNode **vNode, int vPreIndex, int MidIndex, int vLen)

{

    if (vLen == 0) return;

    createNode(vNode, ArrPre[vPreIndex]);

    int MidPos = getMidPos(ArrPre[vPreIndex], MidIndex, MidIndex + vLen);

    if(MidPos == -1)

    {

        CanBuild = 0;

        return;

    }

    createBinaryTree(&((*vNode)->left), vPreIndex+1, MidIndex, MidPos-MidIndex);

    createBinaryTree(&((*vNode)->right), vPreIndex+(MidPos-MidIndex)+1,MidPos+1, vLen-1-(MidPos-MidIndex));

}

void postTravelTree(STreeNode *vNode)

{

    if (vNode == NULL) return;

    postTravelTree(vNode->left);

    postTravelTree(vNode->right);

    printf("%d ", vNode->data);

}

void destroyBinaryTree(STreeNode **vNode)

{

    if (*vNode == NULL) return;

    destroyBinaryTree(&((*vNode)->left));

    destroyBinaryTree(&((*vNode)->right));

    destroyNode(vNode);

}

int main()

{

    int N, i;

    STreeNode *Root;

    while (scanf("%d", &N) != EOF)

    {

        for (i = 0; i < N; ++i) scanf("%d", &ArrPre[i]);

        for (i = 0; i < N; ++i) scanf("%d", &ArrMid[i]);

        CanBuild = 1;

        createBinaryTree(&Root, 0, 0, N);

        if (!CanBuild)

        {

            printf("No\n");

        }

        else

        {

            postTravelTree(Root);

            printf("\n");

        }

        destroyBinaryTree(&Root);

    }

    return 0;

}

/**************************************************************

    Problem: 1385

    User:

    Language: C

    Result: Accepted

    Time:0 ms

    Memory:920 kb

****************************************************************/