二插树是数据结构里永远越不过的一道砍，要想在算法有所提升的话，二插树是我们必须要攻克的。
今天在编程的时候遇到了，所以在这里记录仪下免得以后再忘了。
在举例之前我要先强调一下，做这种题目的时候你要首先记住，必须记住，绝对要记住的东西：
先序遍历访问顺序：根->左->右。
中序遍历访问顺序：左->根->右。
后序遍历访问顺序：左->右->根。
如果你对这个问题也不是很了接，可以拿纸笔一起来。
之后我们来看例题：
先序：1 | 2，4，7 | 3，5，6，8
中序：4，7，2 | 1 | 5，3，8，6
根据访问顺序：在先序遍历中第一个数字，必然是第一个根节点，我们需要找到1在中序中的位置
1，在第四个位置，那么我们可以断定在中序中，1的左孩子群就是4，7，2，右孩子群就是5，3，8，6
那现在的结构就是： 1
-----------------------------/ \
剩余未判断的序列我们来做一个分割：
先序：1 | 2，4，7 | 3，5，6，8
中序：4，7，2 | 1 | 5，3，8，6
之后我们怎么判断左右的孩子群的结构呢？让我们再来重复一边先序和中序的访问顺序：
先序遍历访问顺序：根->左->右。
中序遍历访问顺序：左->根->右。
好，那我们继续来看先序遍历中分组的左孩子群。2，4，7。那我们不妨大胆的根据访问顺序猜测着画一下：
先序： 2 中序： 7
--------- / \ --------- / \
-------- 4 7 ------- 4 2
这怎么办呢？，我们不妨从先序的这个类型来着手，毕竟先序遍历用到的频率比较高。
就把2当作根，剩下我们来看4，7。首先他们肯定不是二的左右孩子，这个根据访问顺序就能看出，在先序中7在4的后面，那么就把7放在4的子孩子，可究竟是左还是右，这我们还要靠中序的信息来推断。
中序中，7也在4的左边，那么根据访问顺序我们可以断定：7是右孩子。
先序：根，左，右
中序：左，根，右
我们就把他想象成排序可能，1，2，3和2，1，3。
随便拿出两个数字，看他们的位置：12，13，23 和：21，23，13。
可以看到唯一不同的一组数就是12和21。
所以12（根左）和21（左根）是逆转的唯一一组，除了这个变化之外其他两组可以说只要一至，基本上就是正确的结构。
（注：这只是个人总结的经验，仅供参考）
那么现在推出的结构是： 1
--------------------------------- / \
------------------------------ 2
----------------------------- / \
---------------------------- 4 *
---------------------------- / \
--------------------------- * 7
好现在我们看右半，为了方便我们重新写一遍序列。
先序：1 | 2，4，7 | 3，5，6，8
中序：4，7，2 | 1 | 5，3，8，6
根据我们之前的原理，那我们看先序，以3为根，在中序中我们看到5在3的前面。
则我们可以判断5，为3的左孩子，那只剩下6和8两个数了。
这两个数列你们看着有没有种熟悉的感觉？对，就是我刚在说的。两个数的位置反转了，
则我们可以得到完整的二插树了： 1
------------------------------------------------ / \
----------------------------------------------- 2 3
---------------------------------------------- / \ / \
--------------------------------------------- 4 * 5 6
--------------------------------------------- / \ / \
-------------------------------------------- * 7 8 *
其他几种推断也是相同的道理，希望对你的学习右帮助。
另贴java代码在下面，携带码的小伙伴可以拿去玩一玩，如果不懂就把输出全部打出来看：
public class Main {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public static void main(String[] args) {
int[] pre = {1,2,4,7,3,5,6,8};
int[] in = {4,7,2,1,5,3,8,6};
TreeNode tn = reConstruction(pre,0,pre.length-1,in,0,in.length-1);
}
private TreeNode reConstruction(int[] pre, int i, int length, int[] in, int i1, int length1) {
if(i>length||i1>length1){
return null;
}
TreeNode node = new TreeNode(pre[i]);
for(int j =i1;j<=length1;j++){
if(pre[i]==in[j]){
node.left = reConstruction(pre,i+1,j+i-i1,in,i1,j-1);
node.right = reConstruction(pre,j+1+i-i1,length,in,j+1,length1);
break;
}
}
return node;
}
}
网友评论