前序遍历+中序遍历重建二叉树

• 题目
• AC代码

本题链接：剑指 Offer 07. 重建二叉树

注：链接题目仅代表和本题大体相似
因为是考研笔试，本题代码以C语言去写

代码解释：本题要求就是给定两个序列：分别为树的前序遍历和树的中序遍历，我们知道，在树的各节点值均不同的情况下，给定一个树的前序遍历+中序遍历 || 后序遍历+中序遍历 || 层序遍历+中序遍历，可以唯一确定出一棵树，这里给出数据结构的相关推导过程：




⭐️上述笔记仅涉及重构二叉树的内容，如果想获得完整【数据结构】树与二叉树的相关笔记请访问博客：树与二叉树 (还未超链接，约12.20日完成超链接)
从上述中我们可以看出，其实重建二叉树可以不断的通过递归去实现，递归划分左右子树的点(根节点)就是就在于在中序遍历中找到这个点，这就是我们下述代码中for循环实现的东西：

int i;
for (i = 0; i < inorder_size; i ++ ){
	if (root -> val == inorder[i]) 
		break;
}

⭐️当然这一步我们可以用哈希表去写，这样时间复杂度会降到O(n)，C++可直接调用哈希函数：STL—map，当然我们在做笔试题的时候是不允许调用函数的，我们也可以手写哈希函数：哈希表，读者可以根据我写的哈希表这个博客去优化改进下述代码，对于考研笔试而言，写成我写的下述代码就已经足够了，并不要求掌握手写哈希函数

代码：

 
struct TreeNode* buildTree(int* preorder, int preorder_size, int* inorder, int inorder_size) {
    if (preorder == NULL || preorder_size == 0 || inorder == NULL || inorder_size == 0){
        return NULL;
    }
    
    struct TreeNode *root = (struct TreeNode*)malloc(sizeof (struct TreeNode));
    root -> val = preorder[0];
    
    int i;
    for (i = 0; i < inorder_size; i ++ ){
        if (root -> val == inorder[i]) 
            break;
    }
    root -> left = buildTree(&preorder[1], i, &inorder[0], i);
    root -> right = buildTree(&preorder[i + 1], preorder_size - i - 1, &inorder[i + 1], inorder_size - i - 1);
    
    return root;
}