当前位置:网站首页>剑指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;
}
}
官方–迭代方法
迭代即非递归方法。
思路可以二叉树遍历的非递归实现作为理论基础。
二叉树的非递归方法感觉很难理解,故待后续有学习需求再来这里补充。
暂时感觉递归够用。看不懂所以不纠结浪费时间了。
边栏推荐
- Kubectl_ Command experience set
- error: expected reference but got (raw string)
- 实现验证码验证
- Fundamentals of concurrent programming (III)
- 手机号码变成空号导致亚马逊账号登陆两步验证失败的恢复网址及方法
- Flutter: self study system
- 抓包整理外篇fiddler———— 会话栏与过滤器[二]
- [combinatorics] permutation and combination (example of permutation and combination)
- Dart: about Libraries
- 云计算未来 — 云原生
猜你喜欢
Is BigDecimal safe to calculate the amount? Look at these five pits~~
PHP export word method (phpword)
为什么我的mysql容器启动不了呢
C language improvement article (wchar_t) character type
Visual studio 2022 downloading and configuring opencv4.5.5
Solve msvcp120d DLL and msvcr120d DLL missing
(构造笔记)ADT与OOP
LeetCode 0556.下一个更大元素 III - 4步讲完
雲計算未來 — 雲原生
Self made pop-up input box, input text, and click to complete the event.
随机推荐
Flutter 退出登录二次确认怎么做才更优雅?
[learning notes] DP status and transfer
Solve msvcp120d DLL and msvcr120d DLL missing
(構造筆記)從類、API、框架三個層面學習如何設計可複用軟件實體的具體技術
Flutter Widget : KeyedSubtree
(构造笔记)从类、API、框架三个层面学习如何设计可复用软件实体的具体技术
【附下载】密码获取工具LaZagne安装及使用
Lambda表达式
Dart: about grpc (I)
Php Export word method (One MHT)
Itext7 uses iexternalsignature container for signature and signature verification
Slf4j log facade
PHP导出word方法(一mht)
Swagger
PHP get the file list and folder list under the folder
Dart: about Libraries
QT OpenGL texture map
2.7 overview of livedata knowledge points
2020-10_ Development experience set
LeetCode 0556.下一个更大元素 III - 4步讲完