前序遍历+中序遍历重建二叉树
题目
本题链接:剑指 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;
}
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码