用先序和中序遍历重建二叉树
2023-02-18 16:26:32 时间
1. 分析
前序遍历:根→左→右
中序遍历:左→根→右
由前序遍历序列pre={1,2,4,7,3,5,6,8}可知根结点是1;
则在中序遍历序列in={4,7,2,1,5,3,8,6}中找到1,便可知1所在位置的左侧是左子树,1所在位置的右侧是右子树;
递归调用:将左子树和右子树分别看成一颗树,将其前序遍历序列、中序遍历序列分别传入到该方法中,便可得到左子树的根结点、右子树的根结点。
此时需要用第一步得到的根结点连接它们;
递归调用的终止条件:直到传入数组为空,说明已经没有节点,直接返回null。
代码
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
//一段树的前序以及对应的中序遍历
if (pre.length==0||in.length==0||pre.length!=in.length){
return null;
}
//确定左子树和右子树的前序和中序
TreeNode rootNode=new TreeNode(pre[0]);
for (int i = 0; i < in.length; i++) {
if (in[i]==pre[0])
{
//左子树前序,中序
rootNode.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
//右子树
rootNode.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
break;
}
}
return rootNode;
}
相关文章
- RxJava 之 create操作符 源码解析
- Rxjava之from系列操作符源码解析
- RxJava之创建操作符源码介绍
- RxJava之timer和interval操作符源码解析
- Java中的12个原子操作类
- Java中的并发工具类
- Java中的线程池
- Executor框架
- RxJava之Schedulers源码介绍
- RxJava subscribeOn和observeOn源码介绍
- Flowable subscribe流程介绍
- RxJava之转换操作符源码介绍
- RxJava之concatMap系列转换操作符源码介绍
- Java并发编程基础
- Java内存模型
- Java并发机制的底层实现原理
- Java中的锁的使用和实现介绍
- Observable subscribe流程介绍
- RxJava之flatMap系列转换操作符
- RxJava之过滤操作符介绍