《剑指offer》面试题6 重建二叉树 Java版
2024-08-29 00:04:30
(由一个二叉树的前序和中序序列重建一颗二叉树)
书中方法:我们要重建一棵二叉树,就要不断地找到根节点和根节点的左子结点和右子节点。注意前序序列, 它的第一个元素就是二叉树的根节点,后面的元素分为它的左子树的前序遍历和右子树的前序遍历。现在的问题是如果光靠前序序列,我们只能找到根节点,但是我们不知道两个子序列的长度,也就无法继续用同样的方法找到子树的根节点。这时候我们就需要一个辅助序列——中序序列,根据它的特性,根节点一定在左子序列和右子序列的中间,这样我们就可以确定两个子序列的长度了。
public TreeNode build(int[] a, int[] b){
if(a.length == 0){
return null;
}
return build(a, 0, a.length-1, b, 0, b.length-1);
}
private TreeNode build(int[] a, int aStart, int aEnd, int[] b, int bStart, int bEnd){
if(aStart > aEnd)return null;
//构建根节点
TreeNode root = new TreeNode(a[aStart]);
//找到根节点在中序序列中的位置
int partition = bStart;
for(int i=bStart; i<=bEnd; i++){
if(b[i] == a[aStart]){
partition = i;
break;
}
}
//在左子序列中继续构建根节点
root.left = build(a, aStart+1, aStart+1+partition-1-bStart,
b, bStart, partition-1);
//在右子序列中继续构建根节点
root.right = build(a, aStart+partition-bStart+1, aEnd,
b, partition+1, bEnd);
//返回构建好的根节点
return root;
}
注:只能用前序+中序或者后序+中序重建二叉树,用前序+后序重建的二叉树不唯一,因为我们不能确定前序序列第一个元素的后面以及后序序列最后一个元素的前面表示的到底是左子树还是右子树。例如一个只有左子树的二叉树3<-2<-1和一个只有右子树的二叉树1->2->3,他们的前序和中序序列是一样的。
最新文章
- 使用javascript和canvas画月半弯
- atitit.压缩算法 ZLib ,gzip ,zip 最佳实践 java .net php
- ubuntu 14.04安装
- 如何把powerpoint幻灯片大小改为标准或宽屏教程【图文】
- phpcms:八、show.html
- Walking Ant(bfs)
- AspUpload组件的安装及使用方法介绍
- linux虚拟机网络配制方法及遇到问题的解决方法
- bootstrap错误警告信息提示
- SpringMVC+jquery.uploadify 上传文件
- Background Media Recovery terminated with ORA-1274 after adding a Datafile (Doc ID 739618.1)
- 阿里云配置 https 证书
- Hibernate 序列生成主键
- (转载)solr实现满足指定距离范围条件的搜索
- tkinter-clock实例
- iOS 9应用开发教程之使用开关滑块控件以及滚动部署视图
- Largest Rectangle in Histogram leetcode java
- emacs配置buffer的快捷键
- scala(9) Monad
- TSL / SSL
热门文章
- LAMP 搭建,wordpress.xcache,powerdns及poweradmin
- jquery input选择器 语法
- HDU 2829 [Lawrence] DP斜率优化
- [BZOJ5249][九省联考2018]IIIDX:线段树+贪心
- Python中的不可变对象类型与可变对象类型
- 为什么要使用 Go 语言,Go 语言的优势在哪里?
- JPA 开发写SQL时候遇见的困难点
- java实现数据库之间批量插入数据
- jsvnadmin访问一直登陆 找不到用户
- 20175212童皓桢 实验三敏捷开发与XP实践实验报告