专栏首页苦逼的码农通过前序+中序和后序+中序来构建二叉树

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

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

在这里插入图片描述

前序 + 中序

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

前序遍历 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:重建二叉树

本文分享自微信公众号 - 苦逼的码农(di201805),作者:stu

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Super Pow:如何高效进行模幂运算

    今天来聊一道与数学运算有关的算法题目,LeetCode 372 题 Super Pow,让你进行巨大的幂运算,然后求余数。

    帅地
  • 二分搜索只能用来查找元素吗?

    最常见的就是教科书上的例子,在有序数组中搜索给定的某个目标值的索引。再推广一点,如果目标值存在重复,修改版的二分查找可以返回目标值的左侧边界索引或者右侧边界索引...

    帅地
  • 详解算法之重建二叉树

    从今天开始,公众号陆陆续续开始插写用动画形式展现算法题,如剑指offer、Leedcode里经典面试题型,同时也会更新数据结构与算法基础、网络原理等知识。

    帅地
  • L2-006. 树的遍历

    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

    指点
  • 数据结构——遍历二叉树

    二叉树的遍历:是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。

    蜻蜓队长
  • 剑指offer 33——二叉搜索树的后序遍历序列

    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

    健程之道
  • 【图解数据结构】 一组动画彻底理解二叉树遍历

    定义:二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

    五分钟学算法
  • Leetcode: Construct Binary Tree from Inorder and Postorder Traversal

    题目: Given inorder and postorder traversal of a tree, construct the binary tree...

    卡尔曼和玻尔兹曼谁曼
  • poj 1915 Knight Moves

    Knight Moves Time Limit: 1000MS Memory Limit: 30000K Total Submissions:...

    attack
  • 前序遍历中序遍历求后序遍历-数组篇

    如果已知前序遍历和中序遍历,那么肯定能够求出后序遍历。正常的思路就是,根据前序遍历和中序遍历,我们把二叉树的结构给描述出来,然后再使用后序遍历。

    chain

扫码关注云+社区

领取腾讯云代金券