根据两序遍历推出第三序以及构建树
数据结构和算法
18 分钟 读完 (大约 2644 个字) 0次访问

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

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

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. 附录：

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

参考/感谢：

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

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

#
fastDFS的安装和springboot完成文件上传
Java实现树的遍历及二叉树可视化
关注我

分类

标签云

DL/ML http lintcode markdown mysql spring springcloud 二分查找 剑指offer 力扣 加密 动态规划 单调栈 回溯 字符串 学习记录 开发 排序 数据结构 栈 树 游戏和引擎 笔试 笔试面试 算法 递归

推荐阅读

推荐阅读

Your browser is out-of-date!

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

×