首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >通过前序+中序和后序+中序来构建二叉树

通过前序+中序和后序+中序来构建二叉树

作者头像
帅地
发布2019-12-24 14:10:25
2.3K0
发布2019-12-24 14:10:25
举报
文章被收录于专栏:苦逼的码农苦逼的码农

首先我们要知道,三种不同遍历方式的过程。看下图很容易理解,并且不容易忘。 前序遍历:根 左 右 中序遍历:左 根 右 后序遍历:左 右 根

在这里插入图片描述

前序 + 中序

题意:给你一个前序遍历和中序遍历,你要构造出一个二叉树。 示例:

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

要想解决这类题目,我们就要掌握遍历的特点

  1. 前序遍历第一位数字一定是这个二叉树的根结点
  2. 中序遍历中,根结点讲序列分为了左右两个区间。左边的区间是左子树的结点集合,右边的区间是右子树的结点集合。

我们能找到根节点,就能找到左子树和右子树的集合,那么这个二叉树是不是就已经有了一个大致的样子。 接下来要做的,就是使用递归去构建出左子树和右子树。

示例过程:

1

2

3 代码:

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //用 HashMap 存储中序遍历,目的是查找方便。因为我们从前序遍历找到根节点后,还要寻找根节点在中序遍历的哪个位置
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++)
            map.put(inorder[i],i);
        return build(preorder, map, 0, preorder.length - 1, 0);
    }

    // 传入了五个参数,分别是:先序序列,中序序列
    // 先序序列的开始,先序序列的结束,中序序列的开始
    public TreeNode build(int[] preorder, HashMap<Integer,Integer> map, int preStart, int preEnd, int inStart){
        // 递归边界
        if(preEnd < preStart)
            return null;
        // 先序序列的第一位是根节点
        TreeNode root = new TreeNode(preorder[preStart]);
        //找到中序序列中,根节点的索引 index
        int rootIndex = map.get(root.val);
        // len 代表左子树的结点个数
        int len = rootIndex - inStart;
        // 左右子树的递归调用
        root.left = build(preorder, map, preStart + 1, preStart + len, inStart);
        root.right = build(preorder, map, preStart + len + 1, preEnd, rootIndex + 1);
        return root;
    }

后序+中序

我们会理解了前序和中序遍历构造二叉树,那么后序和中序构造二叉树就不是难事。 后序序列的特点是,左,右,根。

  1. 找到根结点(后序遍历的最后一位)
  2. 在中序遍历中,找到根结点的位置,划分左右子树,递归构建二叉树。

这里希望各位自行在草稿纸上画一下,二叉树构建过程。

代码:

public TreeNode buildTree(int[] inorder, int[] postorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++)
            map.put(inorder[i],i);
        return build(postorder, map, 0, postorder.length - 1, 0);
    }

    public TreeNode build(int[] postorder, HashMap<Integer,Integer> map, int postStart, int postEnd, int inStart){
        if(postEnd < postStart)
            return null;
        TreeNode root = new TreeNode(postorder[postEnd]);
        int rootIndex = map.get(root.val);
        int len = rootIndex - inStart;
        // 前面与先序遍历是一样的,仅仅是划分左右子树的地方不同。
        root.left = build(postorder, map, postStart, postStart + len - 1, inStart);
        root.right = build(postorder, map, postStart + len, postEnd - 1, rootIndex + 1);
        return root;
    }

两者的比较:

前序遍历

在这里插入图片描述

由图片可以很清晰的看到,前序遍历是根左右,后序遍历是左右根。代码中递归的参数传递,即划分区域就是按照这个图片得到的。没理解代码可以结合图片去看。

二叉树的问题绝大部分都是和三种遍历有关,思考问题的时候,可以从三种遍历的特点入手。

其他二叉树相关

1、详解算法之重建二叉树 2、二叉树的后序遍历(非递归版) 3、二叉树的先序遍历(非递归版) 4、二叉树的中序遍历(非递归版) 5、从上往下打印二叉树 6、二叉搜索树的后序遍历序列 7、剑指offer:二叉树镜像 8、剑指offer:二叉树的子结构 9、剑指offer:重建二叉树

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-12-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 帅地玩编程 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前序 + 中序
  • 后序+中序
    • 其他二叉树相关
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档