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;
}
