由后序序列和先序序列得到二叉树

2021年6月22日 1点热度 0条评论 来源: LawsonAbs

由后序序列和先序序列得到二叉树

1.题意

学过数据结构的都知道,由后序序列和先序序列可以得到二叉树,但是得不到唯一的二叉树。但是如何使用后序和先序得到一棵二叉树呢?这是一个比较有意思的话题。

2.分析

2.1 前提知识
  • 后序序列postOrder:遍历的顺序是LRD,分别代表左子树,右子树,根,意思就是对于一棵树,始终是先输出左子树的部分,再输出右子树的部分,再输出根。这对于树的任何一个子树都是成立的。
  • 先序序列preOrder:遍历顺序是DLR,分别代表根,左子树,右子树。分析同上。
2.2 如何构造?

见下图:

3.代码

这里不提供代码,有兴趣的话,可以看一道pat题,并参看我的题解。【待更新】

    原文作者:LawsonAbs
    原文地址: https://blog.csdn.net/liu16659/article/details/89714971
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。