专栏首页苦逼的码农详解算法之重建二叉树

详解算法之重建二叉树

作者 | 小鹿

来源 | 小鹿动画学编程

写在前边

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

以为无论是面试还是实际项目,对算法的要求也非常的严格,所以小鹿尽最大努力把算法还原成动画形式来讲解,争取让每个人都能看懂算法、学会算法。

1

题目

已知前序遍历为{1,2,4,7,3,5,6,8},中序遍历为{4,7,2,1,5,3,8,6},它的二叉树是怎么样的?

2

基础巩固

根据上述题目所述,我们已知前序遍历和中序遍历,回顾一下,什么是前序遍历?什么是中序遍历?

2.1 前序遍历

前序遍历一颗二叉树,首先输出根节点,然后输出左子节点,最后输出右子节点。

比如,遍历一下二叉树:

颜色变深表示遍历,突出表示输出

2.2 中序遍历

中序遍历一棵二叉树,首先输出左子节点,然后输出输出根节点,最后右子节点。

以上边二叉树为例,通过中序遍历输出。

3

解题思路

既然我们知道了二叉树如何进行前序遍历和中序遍历了,那么已知前序遍历和中序遍历如何反推二叉树呢?

那么问题来了,只知道前序遍历能不能反推二叉树呢?我们就试一下,比如题目中所述,{1,2,4,7,3,5,6,8},根据前序遍历,根、左、右,1 肯定是 根节点,那么一下2,4,7.....哪些是左子节点呢?左子节点有几个呢?很显然我们是不知道的,由此可以得出,只知道前序遍历是不可能反推出二叉树的,中序遍历也是如此,自己可以尝试一下。

那么前序遍历和中序遍历可不可以?那我们要试一下,我们上边通过前序遍历找到第一个根节点就是 1,如图

中序遍历{4,7,2,1,5,3,8,6}的规律又是左、根、右,所以 1 结点在中序遍历中为根,它的左边就是所有左子节点4,7,2,右边为所有的右子节点5,3,8,6

此时我们已经划分左右子节点了,但是左边的子节点中哪些又是根节点呢?我们再回到前序遍历中,根据前序遍历的特点,根、左、右,在从子节点进行划分,那么 1 结点中的子节点谁为根节点呢?

我们一眼就能看出来,就是 2 结点,那么剩余的 4,7 左右结点怎么分呢?我们根据上述再回到中序遍历,找到 2 根节点,根据中序遍历左、根、右的特点,找到 2 结点,那左边的就是左子节点,右边的就是右子节点,我们可以看到,左边有两个数,正是 4 和 7 结点。

右边只有 1 结点,1 结点我们刚刚说了,是根节点,所以以 2 为根节点是没有右子节点的,剩下的数字也是同样的方式区分,自己可以试一下,动手画一画。

我们仔细发现,其实整个层层往下,以及左右,都是相同的解决方式,而且大问题可以分解为小问题,我们下意识就应该想起小鹿之前分享过的知识,那就是递归,既然是递归,就应该有终止条件,终止条件就是当子节点为空时,此时递归结束。

4

测试用例

我们之前的文章强调过,手写代码之前,一定先把测试用例想好,为了能够在手写代码的时候考虑到边界情况,还为了防止你到时候面试涂涂改改。

4.1 普通测试

完全二叉树、非完全二叉树。

4.2 特殊测试

只有左子节点二叉树,只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。

4.3 输入测试

空树、空指针null、前序和中序不匹配。

5

代码实现

JavaScript 版本

Java 版本

C 语言版本

Python 版本

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

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

原始发表时间:2019-10-31

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【二叉树打卡3】二叉树的先序遍历(非递归版)

    二叉树的先序遍历顺序是根-左-右。我们可以采用一个栈来辅助,我们把先序遍历的结果放到一个 ArrayList 容器中作为返回值,具体步骤如下:

    帅地
  • 【二叉树打卡5】二叉树的后序遍历(非递归版)

    二叉树的后序遍历顺序是左-右-根。我们可以采用一个栈来辅助,不过它和前序遍历以及中序遍历还是有点区别的,我们把后序遍历的结果放到一个 LinkedList 容器...

    帅地
  • 【二叉树打卡2】从上往下打印二叉树

    这个像相当于二叉树四种遍历中的层序遍历了,其思想是采用广度优先遍历,借助一个辅助队列,步骤如下:

    帅地
  • 深入理解二叉树的特点

    在计算机科学中,二叉树(Binary tree)是一个连通的无环图,每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“...

    我是攻城师
  • 二叉树的重建

    在http://blog.csdn.net/hacker_zhidian/article/details/60586445这篇文章中我们看了一下二叉树的四种遍历...

    指点
  • 二叉树的四种遍历算法

    二叉树在作为一种重要的数据结构,它的很多算法的思想在很多地方都用到了,比如说大名鼎鼎的 STL 算法模板,里面的优先队列(priority_queue)、集合(...

    指点
  • 令你头疼的[树]

    The first step to accepting yourself is to stop comparing yourself to others.

    小闫同学啊
  • 二叉树非递归版的中序遍历算法

    本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

    double
  • 面试二叉树看这 11 个就够了~

    不知道你有没有这种困惑,虽然刷了很多算法题,当我去面试的时候,面试官让你手写一个算法,可能你对此算法很熟悉,知道实现思路,但是总是不知道该在什么地方写,而且很多...

    Lenis
  • 数据结构(七)

    在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常...

    可爱见见

扫码关注云+社区

领取腾讯云代金券