剑指offer 7# 重建二叉树

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

使用递归的方法, 对于输入的前序遍历中的元素, 寻找中序遍历中的相同元素位置. 在中序遍历中, 这个元素的左边就是节点的左子树, 右边就是右子树.

root->left = buildTree(preorder+1, i, inorder, i);
root->right = buildTree(preorder + i + 1, preorderSize - i - 1, inorder + i + 1, inorderSize - i - 1);
是重点.

左子树的元素数量是从preorder+1起的i个元素, 也是inorder起的i个元素(inorder中的i+1位置就是root)
右子树的计算方法是对左子树的元素做减法: 减去左子树的元素数量和root

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    if(preorderSize <= 0 || inorderSize <= 0 || (preorderSize!=inorderSize)) return NULL;
    struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = preorder[0];
    root -> left = NULL;
    root ->right = NULL;

    int i  = 0;
    while(i <preorderSize &&(preorder[0]!=inorder[i]))i++;
    root->left = buildTree(preorder+1, i, inorder, i);
    root->right = buildTree(preorder + i + 1, preorderSize - i - 1, inorder + i + 1, inorderSize - i - 1);

    return root;


}