【算法】07重建二叉树

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

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

  3
 / \
9  20
  /  \
 15   7

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归法

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize)
{
    if(preorder == NULL || inorder == NULL || preorderSize <= 0 || inorderSize <= 0)
    {
        return NULL;
    }   
 
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = preorder[0];		//根节点

    int i = 0;
    while(inorder[i] != preorder[0])//中序遍历中找出根节点位置
    {
        i++;
    }

    root->left = buildTree(&preorder[1],i,&inorder[0],i);
    root->right = buildTree(&preorder[i+1],preorderSize-i-1,&inorder[i+1],preorderSize-i-1);
    return root;
}