《剑指offer》面试题7:重建二叉树

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
611
文章
12
评论
2020年2月7日23:28:43 评论

一、题目

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。

例如,输入前序遍历序列[1, 2, 4, 7, 3, 5, 6, 8]和中序遍历序列[4, 7, 2, 1, 5, 3, 8, 6],则重建如下图所示的二叉树并输出它的头结点:

《剑指offer》面试题7:重建二叉树

二、解析

根据前序、中序遍历的特性和上面的图形能得到的结论:

  • 前序遍历的第一个元素就是树的根节点。
  • 根节点左边的元素就是左子树,根右边的就是右子树。

图片描述:

《剑指offer》面试题7:重建二叉树

基于这两个特性就可以通过以下方式来构建出一颗二叉树:从前序遍历中确认根节点,再到中序遍历中找到定位到这个根节点,这样就可以拿到对应的左子树和右子树了。然后再按照相同的方式分别得到左右子树的子树,那么整个二叉树就可以构建起来了。

三、代码实现

二叉树节点定义:

二叉树定义:

在二叉树类中实现通过前序遍历和中序遍历构造二叉树的函数:

四、单元测试

单元测试覆盖以下几点:

  • 树为空
  • 树只有一个节点
  • 完全二叉树
  • 满二叉树
  • 不完全二叉树

4.1 树为空

4.2 树只有一个节点

4.3 完全二叉树

4.4 满二叉树

4.5 非完全二叉树

4.6 测试结果

《剑指offer》面试题7:重建二叉树

马谦马谦马谦
  • 本文由 发表于 2020年2月7日23:28:43
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/construct-binary-tree.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: