根据两序遍历推出第三序以及构建树

根据两序遍历推出第三序以及构建树

前言:太久了都快忘了,最近做了一下笔试题遇到这题,发现经常考这种题,先把技巧记录下来,有了技巧后简直不要太轻松

1. 树的三种遍历

  • 前序遍历(根左右)
  • 中序遍历(左根右)
  • 后序遍历(左右根)

Java实现参考这篇博客,不展开了Java实现树的遍历及二叉树可视化

下面我们来看看如何通过前序和中序推出后序以及构造二叉树


2. 前+中–>后

2.1 手写结果

不绕弯子,直接给出技巧再做题

  1. 看前序遍历:第一个为根节点
  2. 看中序遍历:找到步骤1中的根节点,左边的全为左子树,右边的全为右子树
  3. 将左子树看成独立的树,重复步骤1和2,直到只有一个元素,不用脑子就可以做出来啦!

下面进入实战环节(牛客网原题):

对某二叉树进行先序遍历的结果是ABDEFC,中序遍历的结果是DBFEAC,则后序遍历的结果是()

  1. (参照步骤1)发现根节点是A
  2. (参照步骤2)划分出左右子树

  1. (参照步骤1)带着这些左子树看前序遍历,那么前序遍历的顺序是BDEF对吧,将左子树看成是一颗独立的树,于是此时由步骤1得根节点是B

  2. (参照步骤2)在子树中继续划分出左右子树

  1. 还不明白?那么继续,只有一个字母的就直接填上去了,剩下FE,看前序遍历则是EF,既然已经知道是右子树,那么将右子树看成是一颗独立的树,(参照步骤1)于是此时由步骤1得根节点是E
  2. (参照步骤2)划分左右子树,发现只有左子树了,放哪就不必多说了

做多两题,发现掌握了技巧后画出树根本不需要脑子!

画出树后,再做后序遍历就不难了,我就不说了,答案DFEBCA


下面来看代码实现

2.2 Java实现:构造树

力扣105原题:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

老规矩,直接给模板,这是我个人在力扣评论区找到的风格比较喜欢的一套,下面的中+后–>前也是这个模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private int pre = 0, in = 0;	//记录当前前序,中序的下标位置
public TreeNode buildTree(int[] preorder, int[] inorder) {
return recursive(preorder, inorder, Integer.MAX_VALUE);
}

//rootVal是当前节点的值,以当前这个节点作为根节点构造左右子树,没有的话为Integer.MAX_VALUE(比如根节点想象成无限大的某个父节点的左子树)
public TreeNode recursive(int[] preorder, int[] inorder, int rootVal) {
if (pre >= preorder.length) return null; //结束条件是前序下标大于长度
if (inorder[in] == rootVal) { //递归结束条件是找到中序下标
in++;
return null;
}
int curVal = preorder[pre++]; //下一个根节点和值
TreeNode cur = new TreeNode(curVal);
cur.left = recursive(preorder, inorder, curVal);
cur.right = recursive(preorder, inorder, rootVal);
return cur;
}

只需稍微的看一下这两点

  • 一个是pre和in以及他们的++
  • 一个是recursive的第三个参数代表了分界点的值,也就是当前这个节点作为了它的左右子树的根节点,rootVal就是当前这个节点的值。传的参数思考过程如下:

从整棵树的根节点开始想:cur.left这一句就是前序数组中的节点作为了根节点(回想2.1介绍的东西),cur.right这一句的根节点实际上是一开始传入的节点(就是代码注释中:想象成树的根节点是无限大的某个父节点的左子树)那句,因此是传进来的rootVal。能理解吧…


那么说到这里,如何从中序+后序推出前序的代码自己都能修改了吧:pre和in一开始的位置变成末尾,++变成–,先cur.right再cur.left,改好了可以滑到3.2节去对比代码吧!


2.3 Java实现:直接获得后序结果

现在,我们可以通过前序+中序–>构建树–>后序遍历树–>获得后序遍历结果。诚然,代码的话,可以不构建树而直接获得后序遍历结果,我直接贴完整的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class one_zero_five_从前序与中序遍历获得后序遍历 {
@Test
public void test(){
int[] preorder = {3,9,20,15,7};
int[] inorder = {9,3,15,20,7};
totalLen = inorder.length;
int[] res = buildPost(preorder, inorder, 0, totalLen - 1, 0);
System.out.println(Arrays.toString(res));
}

private int post, totalLen;
private int[] postorder = null;

/**
* 直接获得后序结果
* @param preorder 前序数组
* @param inorder 中序数组
* @param start 子树在中序数组中的起始下标
* @param end 子树在中序数组中的结束下标
* @param rootIndex 子树根节点在数组中的下标
* @return 后序数组
*/
public int[] buildPost(int[] preorder, int[] inorder, int start, int end, int rootIndex){
if (postorder == null) postorder = new int[totalLen]; //第一次进入才构建,后期可以考虑放进构造函数
if (start > end) return null;
int i = start; //i代表前序遍历的根节点在中序中的下标
while (i < end && inorder[i] != preorder[rootIndex]) i++;
postorder[post++] = preorder[rootIndex];
buildPost(preorder, inorder, start, i - 1, rootIndex + 1); //构建左子树,start ~ (i - 1),rootIndex:
buildPost(preorder, inorder, i + 1, end, rootIndex + i - start + 1); //构建右子树,(i + 1) ~ end,rootIndex:
return postorder;
}
}

看起来吓人函数体除了注释一共才8行!!其实这个理解起来更容易,

  • start为0,end为len-1,rootIndex一开始为为前序的开始所以是0,那么preorder[rootIndex]就是根节点
  • 在中序中找到这个根节点,i为下标,那么inorder[i]左边为左子树,右边为右子树
  • 那么左子树的范围是start ~ (i - 1),根节点在前序下标为:rootIndex +1
  • 右子树的范围是(i + 1) ~ end,前序是根左右,那么右子树的根节点为:当前根节点位置 + 左子树长度 + 1,左子树长度怎么计算呢?从中序(左根右)那里计算可得i - start就是左子树长度,因此根节点下标为rootIndex + (i - start) + 1

3. 中+后–>前

3.1 手写结果

中序的作用仍然是划分左右子树,后序的作用其实跟前序一样,不过得反过来从后面开始看,最后一个才是根节点

  1. 看后序遍历:最后一个为根节点
  2. 看中序遍历:找到步骤1中的根节点,左边的全为左子树,右边的全为右子树
  3. 将左子树看成独立的树,重复步骤1和2,直到只有一个元素,不用脑子就可以做出来啦!

看题:

中序遍历: GBEDAFCH

后序遍历:GEDBFHCA

我就直接来了

  1. 看后序,根节点是A
  2. 看中序,左边GBED右边FCH

  1. 看后序,要先看右子树(因为后序是“左右根”,之前说了反过来看那么根完了到右),FHC说明根节点是C

  2. 看中序,左边F右边H,左右都只有一个了,完成

  1. 看后序,GEDB说明根节点是B
  2. 看中序,左边单G,右边ED

  1. 看后序,是ED,说明D是根节点

  2. 看中序,左边E,完成


3.2 Java实现:构造树

根据2.2中的套路模板,只需稍微修改一下顺序即可获得正确答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int in, post;
public TreeNode buildTree(int[] inorder, int[] postorder) {
in = inorder.length - 1; //从后面开始
post = postorder.length - 1;
return recursive(inorder, postorder, Integer.MAX_VALUE);
}

public TreeNode recursive(int[] inorder, int[] postorder, int rootVal){
if (post < 0) return null;
if (inorder[in] == rootVal){
in--;
return null;
}
int curVal = postorder[post--];
TreeNode cur = new TreeNode(curVal);
cur.right = recursive(inorder, postorder, curVal); //后序是先右再左
cur.left = recursive(inorder, postorder, rootVal);
return cur;
}

3.3 Java实现:直接获得前序结果

也是跟2.3一样的模板,理解了就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class one_zero_six_从中序与后序遍历获得前序遍历 {

@Test
public void test2(){
int[] inorder = {9,3,15,20,7};
int[] postorder = {9,15,7,20,3};
totalLen = inorder.length;
int[] res = buildPre(inorder, postorder, 0, totalLen - 1, totalLen - 1);
System.out.println(Arrays.toString(res));
}

private int pre, in, post, totalLen;
private int[] preorder = null;
/**
* 直接获得前序结果
* @param inorder 中序数组
* @param postorder 后序数组
* @param start 子树在中序数组中的起始下标
* @param end 子树在中序数组中的结束下标
* @param rootIndex 子树根节点在数组中的下标
* @return 前序数组
*/
public int[] buildPre(int[] inorder, int[] postorder, int start, int end, int rootIndex) {
if (preorder == null) preorder = new int[totalLen];
if (start > end) return null; //结束,随便返回
int i = start; //i为后序数组的某个值在中序数组中的位置
while (i < end && inorder[i] != postorder[rootIndex]) i++; //以i为分隔符,inorder左边为左子树,右边为右子树
preorder[pre++] = postorder[rootIndex];
buildPre(inorder, postorder, start, i - 1, rootIndex - 1 - end + i); //左子树,根节点下标为rootIndex - (end - i + 1)
buildPre(inorder, postorder, i + 1, end, rootIndex - 1); //右子树,根节点下标为rootIndex - 1
return preorder;
}
}
  • start为0,end为len-1,rootIndex一开始为为后序的最后所以是len-1,那么postorder[rootIndex]就是根节点
  • 在中序中找到这个根节点,i为下标,那么inorder[i]左边为左子树,右边为右子树
  • 那么左子树的范围是start ~ (i - 1),根节点下标为:当前根节点下标 - 右子树长度 - 1,右子树长度怎么计算呢?从中序那里计算可得end - i就是右子树长度,因此根节点下标为rootIndex - (end - i) - 1
  • 右子树的范围是(i + 1) ~ end,根节点在后序的下标为rootIndex - 1

4. 前+后–>无法确定

这种情况树不唯一

5. 附录:

搭配上个博客的可视化二叉树工具类一起食用更加,看看你做对了吗

参考/感谢:

构造树的模板提取自力扣官方题解下的朋友十三羽扬

直接获得第三序结果的代码参考了柳神的代码

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×