题目
leetcode 105
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
代码
前序遍历的第一个节点作为根节点，把中序遍历分为根节点的左边节点和右边节点，递归实现
int local(int *nums, int l, int r, int x) {
for (int i = l; i <= r; i++) {
if (nums[i] == x) return i;
}
return -1;
}
//前序遍历的第一个节点作为根节点，把中序遍历分为根节点的左边节点和右边节点，递归实现
struct TreeNode *preInorder(int *preorder, int l1, int r1, int *inorder, int l2, int r2) {
if (l1 > r1) return NULL;
struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
int bit = local(inorder, l2, r2, preorder[l1]);
node->val = preorder[l1];
node->left = preInorder(preorder, l1 + 1, l1 + bit - l2, inorder, l2, bit - 1);
node->right = preInorder(preorder, l1 + bit - l2 + 1, r1, inorder, bit + 1, r2);
return node;
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
struct TreeNode *head;
head = preInorder(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1);
return head;
}