当前位置:网站首页>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;
}
边栏推荐
- Use of kotlin basic common sets list, set and map
- [FAQs for novices on the road] understand program design step by step
- [JS] array flattening
- Kotlin collaboration - start and cancel, scope
- 端午安康,使用祝福话语生成词云吧
- 《MATLAB 神经网络43个案例分析》:第10章 离散Hopfield神经网络的分类——高校科研能力评价
- Dynamic link library nesting example
- JetPack - - -WorkManger
- 动态链接库嵌套样例
- 机器学习笔记 - 监督学习备忘清单
猜你喜欢
Pngquant batch bat and parameter description
MFS details (vii) - - MFS client and Web Monitoring installation configuration
【新手上路常见问答】关于技术管理
【2022高考季】作为一个过来人想说的话
After clicking the uniapp e-commerce H5 embedded applet, the page prompts "the page iframe does not support referencing non business domain names"
Notepad++ settings delete current line shortcut
Kotlin collaboration -- context and exception handling
Kotlin data flow - flow
【虚拟机】 VMware虚拟机占用空间过大解决
RN Metro packaging process and sentry code monitoring
随机推荐
Applet disable native top
Wechat applet uploads pictures (preview deletion limits the size and number of pictures)
Detailed explanation of the player startup process of ijkplayer code walkthrough 2
JNI exception handling
Ijkplayer code walk through H264 unpacker application details
Kotlin basic definition class, initialization and inheritance
Usegeneratedkeys=true configuration
【虚拟机】 VMware虚拟机占用空间过大解决
Applet Use of spaces
【2022高考季】作为一个过来人想说的话
Applet pull-up loading data
Kotlin basic string operation, numeric type conversion and standard library functions
Excel data into database
JetPack - - - LifeCycle、ViewModel、LiveData
Logcat -b events and eventlogtags print the location correspondence of the events log in the code
Recent problems
【新手上路常见问答】一步一步理解程序设计
Recommend a capacity expansion tool to completely solve the problem of insufficient disk space in Disk C and other disks
十五、IO流(一)
MFS details (vii) - - MFS client and Web Monitoring installation configuration