当前位置:网站首页>105. 从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树
2022-06-13 06:20:00 【Mr Gao】
105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
解题代码如下:
int root_preorder(int *preorder,int left,int right){
return preorder[left];
}
int find_root(int* inorder,int left,int right,int val){
int i;
for(i=left;i<=right;i++){
if(inorder[i]==val){
return i;
}
}
return 0;
}
int find_pre(int* preorder,int preleft,int preright,int* inorder,int inleft,int inright){
int i;
int j;
for(i=preleft;i<=preright;i++){
for(j=inleft;j<=inright;j++){
if(preorder[i]==inorder[j]){
return i;
}
}
}
return 0;
}
void create_tree_dfs(int* preorder,int preleft,int preright,int* inorder,int inleft,int inright,struct TreeNode **r){
if(preleft<=preright){
int val=root_preorder(preorder,preleft,preright);
(*r)->val=val;
(*r)->left=(struct TreeNode* )malloc(sizeof(struct TreeNode));
(*r)->right=(struct TreeNode* )malloc(sizeof(struct TreeNode));
int in_root_index=find_root(inorder,inleft,inright,val);
int left_index=find_pre(preorder,preleft,preright,inorder,inleft,in_root_index-1);
// printf("left_index %d |",left_index);
create_tree_dfs(preorder,left_index,left_index+in_root_index-inleft-1,inorder,inleft,in_root_index-1,&((*r)->left));
int right_index=find_pre(preorder,preleft,preright,inorder,in_root_index+1,inright);
// printf("right_index %d |",right_index);
create_tree_dfs(preorder,right_index,right_index+inright-in_root_index-1,inorder,in_root_index+1,inright,&((*r)->right));
}
else{
*(r)=NULL;
}
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
struct TreeNode* r=(struct TreeNode* )malloc(sizeof(struct TreeNode));
create_tree_dfs(preorder,0,preorderSize-1,inorder,0,inorderSize-1,&r);
return r;
}
边栏推荐
- Wechat applet (get location)
- Applet export (use) public function, public data
- Detailed explanation of the player startup process of ijkplayer code walkthrough 2
- Learning records countless questions (JS)
- JVM基础
- 动态链接库嵌套样例
- SSM框架整合--->简单后台管理
- Excel data into database
- Kotlin basic definition class, initialization and inheritance
- [virtual machine] VMware virtual machine occupies too much space. Solution
猜你喜欢
Explication détaillée du triangle Yang hui
数据在内存中的存储(C语言)
【新手上路常见问答】一步一步理解程序设计
《MATLAB 神经网络43个案例分析》:第10章 离散Hopfield神经网络的分类——高校科研能力评价
Failed to extract manifest from apk: processexception:%1 is not a valid Win32 Application.
Pngquant batch bat and parameter description
无刷直流电机矢量控制(四):基于滑模观测器的无传感器控制
[SketchUp 2021] CAD file import and modeling in the sketch master (establish elevation model in the sketch master by using CAD drawings), and the sketch master exports 2D, 3D and elevation effects of
【2022高考季】作为一个过来人想说的话
MFS details (vii) - - MFS client and Web Monitoring installation configuration
随机推荐
'ipconfig' is not an internal or external command, nor is it a runnable program or batch file.
Notes on wechat applet development
【sketchup 2021】草图大师中CAD文件的导入与建模(利用cad图纸在草图大师中建立立面模型)、草图大师导出成品为dwg格式的二维、三维、立面效果到cad中打开预览】
Array operations in JS
线程池学习
Construction and verification of Alibaba cloud server webrtc system
JVM基础
Kotlin foundation extension
Cocos creator compilation game cannot read property 'polygonpolygon' of undefined
【sketchup 2021】草图大师的图像输出与渲染之样式说明【边线设置、平面设置、背景设置、水印设置、建模设置、天空背景创建天空、利用水印背景创建天空(重要)】
Wechat applet (get location)
Kotlin data flow - flow
Kotlin basic objects, classes and interfaces
ADB shell sendent debug input event
package-lock. json
[JS] handwriting call(), apply(), bind()
Time complexity and space complexity
JS to realize bidirectional data binding
Dragon Boat Festival wellbeing, use blessing words to generate word cloud
Free screen recording software captura download and installation