文章目录
- 题目
- AC代码
题目
本题链接：剑指 Offer 07. 重建二叉树
注：链接题目仅代表和本题大体相似
因为是考研笔试，本题代码以C语言去写
AC代码
代码解释：本题要求就是给定两个序列：分别为树的前序遍历和树的中序遍历，我们知道，在树的各节点值均不同的情况下，给定一个树的💘前序遍历+中序遍历💘 || 💘后序遍历+中序遍历💘 || 💘层序遍历+中序遍历💘，可以唯一确定出一棵树，这里给出数据结构的相关推导过程：
⭐️上述笔记仅涉及重构二叉树的内容，如果想获得完整【数据结构】树与二叉树的相关笔记请访问博客：树与二叉树 (还未超链接，约12.20日完成超链接)
从上述中我们可以看出，其实重建二叉树可以不断的通过递归去实现，递归划分左右子树的点(根节点)就是就在于在中序遍历中找到这个点，这就是我们下述代码中for循环实现的东西：
int i; for (i = 0; i < inorder_size; i ++ ){ if (root -> val == inorder[i]) break; }
⭐️当然这一步我们可以用哈希表去写，这样时间复杂度会降到O(n)，C++可直接调用哈希函数：STL—map，当然我们在做笔试题的时候是不允许调用函数的，我们也可以手写哈希函数：哈希表，读者可以根据我写的哈希表这个博客去优化改进下述代码，对于考研笔试而言，写成我写的下述代码就已经足够了，并不要求掌握手写哈希函数
代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ 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; }
