当前位置:网站首页>剑指Offer07. 重建二叉树
剑指Offer07. 重建二叉树
2022-07-03 11:50:00 【伍六琪】
剑指Offer07. 重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
限制:
0 <= 节点个数 <= 5000
JAVA代码
递归方法
参考了天勤书内的解法。
**设计思想:**先序遍历序列中第一个元素x即为树的根结点数值。在中序遍历中找到x,利用x将中序遍历的数组分为了两个子序列,左边序列构成树的左子树,右边序列构成树的右子树,再对左右两个子序列用同样的方法处理,直到处理的子序列只剩下一个元素时,二叉树构造完成。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
TreeNode node = createTree(preorder,inorder,0,n-1,0,n-1);
return node;
}
//构建二叉树
public TreeNode createTree(int[] preorder, int[] inorder,int L1,int R1,int L2,int R2){
TreeNode node;
int i;
if(L1>R1){
return null;
}
node = new TreeNode();
node.left=node.right=null;
for(i = L2;i<=R2;++i){
if(inorder[i]==preorder[L1]){
break;
}
}
node.val = inorder[i];
node.left = createTree(preorder,inorder,L1+1,L1+i-L2,L2,i-1);
node.right = createTree(preorder,inorder,L1+i-L2+1,R1,i+1,R2);
return node;
}
}
官方–迭代方法
迭代即非递归方法。
思路可以二叉树遍历的非递归实现作为理论基础。
二叉树的非递归方法感觉很难理解,故待后续有学习需求再来这里补充。
暂时感觉递归够用。看不懂所以不纠结浪费时间了。
边栏推荐
- Kubernetes three dozen probes and probe mode
- Redis
- Use bloc to build a page instance of shutter
- Flutter 退出登录二次确认怎么做才更优雅?
- 网络通讯之Socket-Tcp(一)
- Wechat applet - basic content
- Download address and installation tutorial of vs2015
- [combinatorics] permutation and combination (summary of permutation and combination content | selection problem | set permutation | set combination)
- 2.6 preliminary cognition of synergetic couroutines
- Optimize interface performance
猜你喜欢
Integer string int mutual conversion
云计算未来 — 云原生
During FTP login, the error "530 login incorrect.login failed" is reported
QT OpenGL texture map
1-2 project technology selection and structure
2.8 overview of ViewModel knowledge
win10 上PHP artisan storage:link 出现 symlink (): Protocol error的解决办法
[MySQL special] read lock and write lock
Symlink(): solution to protocol error in PHP artisan storage:link on win10
PHP导出word方法(一mht)
随机推荐
Lambda expression
1-2 project technology selection and structure
2.6 preliminary cognition of synergetic couroutines
Simple factory and factory method mode
If you can't learn, you have to learn. Jetpack compose writes an im app (II)
Flutter 退出登录二次确认怎么做才更优雅?
Quantitative calculation research
If you can't learn, you have to learn. Jetpack compose writes an im app (I)
Pki/ca and digital certificate
repo Manifest Format
win10 上PHP artisan storage:link 出现 symlink (): Protocol error的解决办法
pragma-pack语法与使用
JVM内存模型
typeScript
ES6新特性
(构造笔记)GRASP学习心得
【附下载】密码获取工具LaZagne安装及使用
Integer string int mutual conversion
Slf4j log facade
wpa_ cli