leetcode105:Construct Binary Tree from Preorder and Inorder Traversal
2024-08-27 16:13:37
题目:
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
解题思路分析:
前序遍历首先遍历根节点,然后依次遍历左右子树
中序遍历首先遍历左子树,然后遍历根结点,最后遍历右子树
根据二者的特点,前序遍历的首节点就是根结点,然后在中序序列中找出该结点位置(index),则该结点之前的为左子树结点,该节点之后为右子树结点;
同样对于前序序列,首结点之后的index个结点为左子树结点,剩余的节点为右子树结点;
最后,递归建立子树即可。
java代码:
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || preorder.length == 0){
return null;
} int flag = preorder[0];
TreeNode root = new TreeNode(flag);
int i = 0;
for(i=0; i<inorder.length; i++){
if(flag == inorder[i]){
break;
}
} int[] pre_left, pre_right, in_left, in_right;
pre_left = new int[i];
for(int j=1; j<=i;j++){
pre_left[j-1] = preorder[j];
}
pre_right = new int[preorder.length-i-1];
for(int j=i+1; j<preorder.length;j++){
pre_right[j-i-1] = preorder[j];
} in_left = new int[i];
for(int j=0;j<i;j++){
in_left[j] = inorder[j];
}
in_right = new int[inorder.length-i-1];
for(int j=i+1; j<inorder.length; j++){
in_right[j-i-1] = inorder[j];
}
root.left = buildTree(pre_left,in_left);
root.right = buildTree(pre_right,in_right); return root; } }
最新文章
- C# 多線程&;BackgroundWorker概念入門教程
- MySQL的几个概念:主键,外键,索引,唯一索引
- .NET项目工程生成一份项目帮助文档chm--Sandcastle工具
- AngularJs angular.element
- sqlplus 设置
- java工具类包
- [Ubuntu] Ubuntu搭建VPN服务器pptpd
- Java中正则Matcher类的matches()、lookAt()和find()的区别<;转>;
- JQuery Dialog 禁用X按钮关闭对话框,-摘自网络
- [BZOJ1003] [ZJOI2006] 物流运输trans (最短路 &; dp)
- Collections -- OrderedDict类
- css中关于单位的一些问题
- 如何向微软 Docs 和本地化社区提交翻译贡献
- linux系统root密码忘了怎么办 三种方法快速找回root密码
- html5<;embed>;的完整属性
- 41-2:和为S的连续正数序列
- Android ANR异常及解决方法
- 使用InstallUtil安装及卸载Windows服务的具体操作 Visual Studio 2012版本
- 一、并行编程 - 数据并行 System.Threading.Tasks.Parallel 类
- [美团 CodeM 初赛 Round A]数列互质