Construct Binary Tree from Inorder and Postorder Traversal Traversal leetcode java
2024-10-04 03:30:27
题目:
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
题解:
这道题跟pre+in一样的方法做,只不过找左子树右子树的位置不同而已。
/ \ / \ / \ 对于上图的树来说,
index: 0 1 2 3 4 5 6
中序遍历为: 4 2 5 1 6 3 7
后续遍历为: 4 5 2 6 7 3
为了清晰表示,我给节点上了颜色,红色是根节点,蓝色为左子树,绿色为右子树。
可以发现的规律是:
1. 中序遍历中根节点是左子树右子树的分割点。
2. 后续遍历的最后一个节点为根节点。 同样根据中序遍历找到根节点的位置,然后顺势计算出左子树串的长度。在后序遍历中分割出左子树串和右子树串,递归的建立左子树和右子树。
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
}
public TreeNode buildTree(int[] in, int inStart, int inEnd, int[] post, int postStart, int postEnd){
if(inStart > inEnd || postStart > postEnd){
return null;
}
int rootVal = post[postEnd];
int rootIndex = 0;
for(int i = inStart; i <= inEnd; i++){
if(in[i] == rootVal){
rootIndex = i;
break;
}
}
int len = rootIndex - inStart;
TreeNode root = new TreeNode(rootVal);
root.left = buildTree(in, inStart, rootIndex-1, post, postStart, postStart+len-1);
root.right = buildTree(in, rootIndex+1, inEnd, post, postStart+len, postEnd-1);
return root;
}
最新文章
- Visual Stdio 无法直接启动带有“类库输出类型”的项目若要调试此项目,请在此解决方案中添加一个引用库项目的可执行项目。将这个可执行项目设置为启动项目!
- 在树霉派上配置LAMP
- tomcat 的优化配置
- xcode 插件地址
- php随笔(一)
- ZBrush中的纹理-水手该怎样进行绘制
- winform继承窗体,无法修改父窗体控件问题处理笔记
- Loadrunner:场景中添加负载生成器
- Ant学习---第四节:Ant属性的介绍
- 使用SQL脚本访问操作远程数据库
- Python 爬虫——抖音App视频抓包
- Linux命令-cut篇
- POJ 3264 Balanced Lineup 【线段树】
- 关于SQL Server将一列的多行内容拼接成一行的问题讨论【转】
- blob对象的应用
- Jquery 组 表单验证
- codeforces 741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
- 转: 用 Eclipse 平台进行 C/C++ 开发
- 解决pl/sql 查询数据中文显示成?
- python安装openSSL
热门文章
- 获取当前页面url中的参数 coffeescript+node.js+angular
- 图的遍历 之 深搜dfs
- 牛客OI赛制测试赛3游记
- 【原】Spring整合Redis(第一篇)—SDR简述
- HDU 4453 Looploop (伸展树splay tree)
- SystemParametersinfo的用法(一)
- iOS sqlite 使用事务操作数据库
- Javascript 身份证号获得出生日期、获得性别、检查身份证号码
- 批量生成protoBuf到cs文件
- WordPress主题开发实例:get_term_by()获取指定分类链接