# 106 从中序与后序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode *build(int *preorder, int preorderStart, int preorderEnd, int *inorder, int inorderStart, int inorderEnd)
{
   if(inorderStart > inorderEnd) return NULL;

   struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
   root->val = preorder[preorderStart];
   int j;
   for(j = inorderStart; j <= inorderEnd; ++j)
   {
       if(inorder[j]== root->val) break;
   }
   int lenght = inorderEnd -j;

   int leftpreStart = preorderStart + 1;
   int leftpreorderEnd = preorderStart + lenght;
   int leftinorderStart = j+1;
   int leftinorderEnd = inorderEnd;
   root->right = build(preorder, leftpreStart, leftpreorderEnd, inorder, leftinorderStart, leftinorderEnd);

   int rightpreorderStart = leftpreorderEnd + 1;
    int rightpreorderEnd = preorderEnd;
    int rightinorderStart = inorderStart;
    int rightinorderEnd =  j-1;
   root->left = build(preorder, rightpreorderStart, rightpreorderEnd, inorder, rightinorderStart, rightinorderEnd);

   return root;
}

void inverseArr(int *arr, int arrSize)
{
    int i,j;
    for(i = 0, j = arrSize-1; i < arrSize / 2; ++i,--j)
    {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
   inverseArr(postorder, postorderSize);
   return build(postorder, 0, postorderSize-1, inorder, 0, inorderSize-1);
}

代码修改自

基本思想是， 后续遍历的 逆遍历 是。中 右 左 与 前序的 中 左 右 只是 左右顺序换一下就好了。