今天刷问题的时候遇到了这个二叉树问题,这是数据结构中的重点知识,但是学习一年多了,很多东西都被遗忘了,所以今天我把它捡起来了。
问题基础知识的引申前序遍历中序遍历后序遍历问题求解
主题
请输入某二叉树的先序扫描和中序扫描的结果,重建该二叉树。 假设输入的起始和中间遍历结果不包含重复的数字。 例如,输入{1、2、4、7、3、5、6、8}和中顺序扫描序列{4、7、2、1、5、3、8、6}将重建二叉树并返回。
当基础知识铺垫得到这个问题的时候,我只知道排头,但我忘了排头是什么意思。 请来温故。
预读遍历是指按照以下顺序访问各个节点的规则
1 .先访问根节点
2 .首先遍历左边的树
3 .首先遍历右边的子树
例如
我们a节点的访问顺序是A-B-C
这是普通的二叉树
首先,根据遍历规则
A-B-D-G-H-C-E-F-I
这里,在b的情况下,由于到达了b的节点,所以若将b的节点设为根节点,则具有与先扫描,接着的理论相同的道理
中序扫描中序扫描规则:
中序扫描左部分树接入根节点中序扫描右部分树的中序和先序是根节点后接入的区别;
所以根据上面的规则
我们的访问顺序是G-D-H-B-A-E-C-I-F
注意: I是左子树
前后遍历规则:
按后序遍历左侧子树按正在遍历右侧子树访问根节点的访问顺序G-H-D-B-E-I-F-C-A
了解这些基础知识后,看看我们问题的解法
解决问题后,它会告诉你如何遍历二叉树。 求一下这个二叉树吧。
已知的主题是先前的遍历序列{1、2、4、7、3、5、6、8}和中序遍历序列{4、7、2、1、5、3、8、6}
从最初的遍历规则中知道:
根节点为{1}
中顺遍历规则中知道:
左边的树是{ 4,7,2 }
根节点为{1}
右边的子树是{5、3、8、6}
我们用左边的子树和右边的子树重复刚才的操作,
左子树(中顺扫描为{ 4,7,2 }先顺为{ 2,4,7 }
根节点为{1}{2}
左子树的{ 4,7 }左子树排名为{ 4,7 }中排名为{ 4,7 },因此{7}为{4}的右子树
如右部分树那样,中顺扫描为{5、3、8、6}先顺扫描为{3、5、6、8}
{3}是根节点
{1}左子树{2}{3}
右侧子树{6、8}的开头为{6、8}中顺序为{8、6},因此该右侧子树的左节点为{8}根节点为{6};
得到的二叉树
java版
/* * definitionforbinarytree *公共类treenode { * intval; * TreeNode left; * TreeNode right; *treenode(intx ) { val=x; } * } */import java.util.Arrays; 公共类解决方案{ publictreenodereconstructbinarytree (int [ ] pre,int [] in ) {if ) pre.length==0} { return null for(intI=0; i in.length; I ) if(pre[0]==in[I] ) node=newtreenode(pre[0] ); node.left=reconstructbinarytree (arrays.copyofrange (pre,1,i 1),arrays.copyofrange (in,0,I ) ) ) node.rige i 1,pre.length ),Arrays.copyofrange(in,i 1,in } }返回节点; } php版
? PHP/*类treenode { var $ val; var $left=NULL; var $ right=空值; function__construct($val ) { $this-val=$val; } */functionreconstructbinarytree ($ pre,$vin ) ) if (! 计数($ pre ) ) { return null; }$node=newtreenode($pre[0]; $I=array_search($pre[0],$vin ); $ node-left=reconstructbinarytree (array_slice ) $pre,1,$i ),array _ slice ) $vin,0,$i ); $ node-right=reconstructbinarytree (array _ slice )、$pre、$i 1 )、array _ slice ($ vin、$i 1 ) ); 返回$节点; }与上述记录几乎是递归的。 写了两种,想法一样。 请认为权重熟悉函数。 哈哈哈
在吐槽中,我不知道arrays.copyofrange(pre,1,i 1)这个函数,所以百度了半天。
以前我觉得用php写代码是找php工作的好方法,但有时用php版太简单了。 以后都写了。