《剑指Offer》-004 -Java版二叉树先序和中序遍历返回原二叉树
2024-10-21 00:44:06
如题 (总结要点)
- 注意空值
- 假定数据是没有问题的
- 前序(根左右) ,中序(左根右), 故每次的第一个节点就是根节点
- 没用数组的库函数,自己手写了两个方法
- 用Java代码写二叉树很舒服, 没有啥指针,直接赋值就行了!毕竟Java除了基本数据类型传参是形参, 其余都是实参传递.
- 原文链接 : https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
借鉴学习文章列表
- 链接1:
- 链接2:
ALiBaBaJavaCodingGuideLines有话说 :
1.题目
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回
2. Solution代码
/**
* FileName: ${FILENAME}
* 类的详细说明 : 1. 注意空值
* 2. 假定数据是没有问题的
* 3.前序(根左右) ,中序(左根右), 故每次的第一个节点就是根节点
* @author SongZeShan
* @version 1.0
* @Date 2019/7/11 18:10
*/
public class Solution {
/**重建出该二叉树*/
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length==0||in.length==0||pre.length!=in.length){
return null;
}
//建树,根节点赋值
TreeNode treeNode = new TreeNode(pre[0]);
int index = indexOf(in,pre[0]);
//左子树长度为index-1
treeNode.left = reConstructBinaryTree(copyRange(pre, 1, index), copyRange(in, 0, index-1));
//右子树为长度为in.length-index
treeNode.right = reConstructBinaryTree(copyRange(pre, index+1, pre.length-1), copyRange(in, index+1, pre.length-1));
return treeNode;
}
/**复制下标*/
private int[] copyRange(int arr[],int beg,int end){
int []newArr = new int[end-beg+1];
for(int i=beg;i<=end;i++){
newArr[i-beg]=arr[i];
}
return newArr;
}
/**查找key值,返回索引index*/
private int indexOf(int []arr,int key){
for(int i=0;i<arr.length;i++){
if(key==arr[i]){
return i;
}
}
return -1;
}
}
3.TreeNode 二叉树代码
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
4.测试
/**
* FileName: ${FILENAME}
* 类的详细说明
*
* @author SongZeShan
* @version 1.0
* @Date 2019/7/11 18:10
*/
public class Test {
public static void main(String[] args) {
Solution solution = new Solution();
int pre[] = {1,2,4,7,3,5,6,8};
int in[] = {4,7,2,1,5,3,8,6};
TreeNode treeNode = solution.reConstructBinaryTree(pre,in );
//输出测试
preOrder(treeNode);
System.out.println();
midOrder(treeNode);
}
/**遍历一次二叉树先序输出*/
private static void preOrder(TreeNode node){
if(node==null){
return ;
}
System.out.print(node.val+"\t");
preOrder(node.left);
preOrder(node.right);
}
/**遍历一次二叉树中序输出*/
private static void midOrder(TreeNode node){
if(node==null){
return ;
}
midOrder(node.left);
System.out.print(node.val+"\t");
midOrder(node.right);
}
}
测试结果 ,和原答案一模一样
1 2 4 7 3 5 6 8
4 7 2 1 5 3 8 6
Process finished with exit code 0
最新文章
- java类
- centos7 服务管理
- HDU-4526 威威猫系列故事——拼车记 动态规划
- hdu3966 树链剖分+成段更新
- JQuery事件手册
- Python中split()函数的用法及实际使用示例
- android 网络_网络图片查看器
- ios开发之触摸&手势识别
- 一些linux的问题
- STM32 TIM重映射
- hibernate学习五（关系映射多对一与一对多）
- php-fpm 启动参数及重要配置详解<转>
- SMACSS:一个关于CSS的最佳实践-3.Layout Rules
- Swift - 浮点数转换成整数（四舍五入与直接截断）
- android jni——helloworld
- Eclipse代码块折叠插件，安装使用
- 小程序css--view标签下英文不换行，中文会自动换行
- 深入web开发之webserver/servlet容器
- TensorFlow模型保存和加载方法
- 缓存算法：LRU、LFU、FIFO