Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

分析

从前序和中序构造二叉树，使用递归的思想依次找到根节点并构造左右子树，C代码如下已通过。

/**
 * 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)
        return NULL;
    int root=preorder[0];
    struct TreeNode *tree=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    tree->val=root;
    int i;
    for(i=0;i<inorderSize;i++)
        if(inorder[i]==root)
            break;
    tree->left=buildTree(preorder+1,i,inorder,i);
    tree->right=buildTree(preorder+i+1,inorderSize-i-1,inorder+i+1,inorderSize-i-1);
    return tree;
}