文档章节

还原二叉树

Cobbage
 Cobbage
发布于 2015/04/19 00:16
字数 412
阅读 32
收藏 0

一、还原二叉树

      先序、中序

      后序、中序

二、先序和中序的还原

----------------------------------------------
                            A
		             / \
			     B   C
			    / \  / \
			   D   E G  F           
----------------------------------------------
先序遍历结果:ABDECGF


中序遍历结果:DBEAGCF

先序中每个树的节点 左子树  相邻的节点但是要在先序中寻找的

                          右子树  先序中树的节点距离+先序中的位置 下一个就是右子树

例如:B   在先序 D [B] E

        B的下一个节点在左子树木中D可以找的到

                              右子树木中序B距离1 那么右子树在先序中+这个距离的下一个


/**
 *
 * 先序 中序
 */
public class ConstructBinaryTree {

	public TreeNode buildTree(int[] preorder, int[] inorder) {
	       return findTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
			
			public TreeNode findTree(int[] preorder,int preStart,int preEnd,int[] inorder,int inIndex,int inEnd){
				         if(preStart>=preorder.length||inIndex>inEnd)
				        	 return null;
				         
				         int i=inIndex;
				         
				         while(i<=inEnd){
				             if(preorder[preStart]==inorder[i++])
				            	 break;
				         }
				         
				         TreeNode tn=new TreeNode(preorder[preStart]);
				         
		                 tn.left=findTree(preorder,preStart+1,preEnd,inorder,inIndex,i-2);
		                 tn.right=findTree(preorder,preStart+i-inIndex,preEnd,inorder,i,inEnd);
				
				return tn;
			}
		
		public static void main(String[] args) {
			ConstructBinaryTree cbt=new ConstructBinaryTree();
			cbt.buildTree(new int[]{1,2,3}, new int[]{1,2,3});
		}
}


三、后序和先序的还原

后序遍历结果:DEBGFCA

中序遍历结果:DBEAGCF

反过来就是啦 右子树就是左边的

                  左子树就是 左边开始+距离-1

/**
 *
 * 后序 中序
 */
public class ConstructBinaryTreeTwo {

	public TreeNode buildTree(int[] inorder, int[] postorder) {
	       return findTree(postorder,postorder.length-1,0,inorder,0,inorder.length-1);
    }
			
	public TreeNode findTree(int[] postorder,int postEnd,int postStart,int[] inorder,int inIndex,int inEnd){
		   if(postEnd<postStart||inIndex>inEnd)
				   return null;
				         
		    int i=inIndex;
		    while(i<=inEnd){
				   if(postorder[postEnd]==inorder[i++])
				         break;
				 }
				         
	        TreeNode tn=new TreeNode(postorder[postEnd]);
		    tn.left=findTree(postorder,postStart+(i-inIndex-1),postStart,inorder,inIndex,i-2);
		    tn.right=findTree(postorder,postEnd-1,postStart+(i-inIndex-1),inorder,i,inEnd);
				
		    return tn;
}
		
		public static void main(String[] args) {
			ConstructBinaryTreeTwo cbt=new ConstructBinaryTreeTwo();
			cbt.buildTree(new int[]{1,3,2}, new int[]{3,2,1});
		}
}






© 著作权归作者所有

Cobbage

Cobbage

粉丝 56
博文 154
码字总数 74922
作品 1
闵行
QA/测试工程师
私信 提问
小蚂蚁学习数据结构(11)——二叉树的遍历

操作(树的遍历一般指的是二叉树遍历) 经常考的,树的遍历和已知两种遍历求原始二叉树 遍历 先序遍历 【先访问根节点】 先访问跟节点 再先序访问左子树 在先序访问右子树 中序遍历 【中间访...

嗜学如命的小蚂蚁
2016/01/08
65
0
通过二叉树的先序遍历和中序遍历序列,还原这棵二叉树。

由二叉树的先序遍历和中序遍历序列能确定唯一的一棵二叉树。 由二叉树的先序遍历可以确定根节点;知道根节点以后,由二叉树的中序遍历可以确定此根节点的左子树节点集合、右子树节点集合。 ...

G_66_hero
2018/09/15
0
0
根绝已知的遍历顺序(前序+中序||中序+后序)还原二叉树详解(转)

文章转自这里 最近做PAT遇到了还原二叉树的问题,其实,这个算法虽是基础算法,可是当真正比赛或者考试的时候不看模板还是不好写的,因为递归的变量是要严格控制住的。 具体方法如下: 面试题...

语海与冰
2018/11/25
0
0
[LeetCode] Serialize and Deserialize Binary Tree 二叉树的序列化和去序列化

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a networ......

机器的心脏
2017/12/15
0
0
根据前序遍历和中序遍历结果还原二叉树

本文代码为java代码 一、二叉树 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根节点和两棵互不相交的,分别称为根节点的左子树和右子树...

fyzzz9
07/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周日乱弹 —— 我,小小编辑,食人族酋长

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @宇辰OSC :分享娃娃的单曲《飘洋过海来看你》: #今日歌曲推荐# 《飘洋过海来看你》- 娃娃 手机党少年们想听歌,请使劲儿戳(这里) @宇辰OSC...

小小编辑
59分钟前
127
7
spring cloud

一、从面试题入手 1.1、什么事微服务 1.2、微服务之间如何独立通讯的 1.3、springCloud和Dubbo有哪些区别 1.通信机制:DUbbo基于RPC远程过程调用;微服务cloud基于http restFUL API 1.4、spr...

榴莲黑芝麻糊
今天
2
0
Executor线程池原理与源码解读

线程池为线程生命周期的开销和资源不足问题提供了解决方 案。通过对多个任务重用线程,线程创建的开销被分摊到了多个任务上。 线程实现方式 Thread、Runnable、Callable //实现Runnable接口的...

小强的进阶之路
昨天
6
0
maven 环境隔离

解决问题 即 在 resource 文件夹下面 ,新增对应的资源配置文件夹,对应 开发,测试,生产的不同的配置内容 <resources> <resource> <directory>src/main/resources.${deplo......

之渊
昨天
8
0
详解箭头函数和普通函数的区别以及箭头函数的注意事项、不适用场景

箭头函数是ES6的API,相信很多人都知道,因为其语法上相对于普通函数更简洁,深受大家的喜爱。就是这种我们日常开发中一直在使用的API,大部分同学却对它的了解程度还是不够深... 普通函数和...

OBKoro1
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部