首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

由中序遍历和后序遍历构造二叉树

中序遍历和后序遍历是二叉树遍历的两种方式。中序遍历是指先遍历左子树,然后访问根节点,最后遍历右子树;后序遍历是指先遍历左子树,然后遍历右子树,最后访问根节点。

根据中序遍历和后序遍历的结果,可以构造出原始的二叉树。具体的构造过程如下:

  1. 后序遍历的最后一个元素即为二叉树的根节点。
  2. 在中序遍历中找到根节点的位置,根节点左边的元素为左子树的中序遍历结果,右边的元素为右子树的中序遍历结果。
  3. 根据左子树的中序遍历结果的长度,可以在后序遍历中确定左子树的后序遍历结果和右子树的后序遍历结果。
  4. 递归地对左子树和右子树进行构造,直到所有节点都被构造完毕。

下面是一个示例:

中序遍历序列:[4, 2, 5, 1, 6, 3, 7] 后序遍历序列:[4, 5, 2, 6, 7, 3, 1]

根据后序遍历的最后一个元素1,可以确定根节点为1。在中序遍历中找到1的位置,可以将中序遍历序列分为左子树和右子树:

左子树的中序遍历序列:[4, 2, 5] 右子树的中序遍历序列:[6, 3, 7]

根据左子树的中序遍历序列的长度,可以确定左子树的后序遍历序列和右子树的后序遍历序列:

左子树的后序遍历序列:[4, 5, 2] 右子树的后序遍历序列:[6, 7, 3]

对左子树和右子树进行递归构造,得到左子树和右子树的二叉树。将根节点1与左子树和右子树连接起来,即可得到原始的二叉树。

这个问题中没有提到具体的云计算相关内容,因此无法给出腾讯云相关产品和产品介绍链接地址。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

由中遍历后序遍历还原二叉树_二叉树的中序列

二叉树的前序遍历、中遍历后序遍历之间还原二叉树 1、概念 (1)前序遍历 a、访问根节点;b、前序遍历左子树;c、前序遍历右子树。...2、前序遍历遍历还原二叉树 思想如下: a、根据前序遍历结果,第一个元素为二叉树的根结点; b、观察中遍历结果,根结点左侧的为左子树,若左子树根结点前(后)再无任何元素,则左(右...中遍历:CDFEGHAB 求得后序遍历结果为:CFHGEDBA 3、中遍历后序遍历还原二叉树 思想如下: a、根据后序遍历结果,最后一个元素为二叉树的根结点; b、观察中遍历结果...例: 已知 中遍历:HDIBJEKALFMCNGO 后序遍历: HIDJKEBLMFNOGCA 按照上述步骤先画出二叉树,然后在进行求解前序遍历结果。...结果为: ABDHIEJKCFLMGNO 练习:可参考前序遍历遍历的练习 4、前序遍历后序遍历还原二叉树 已知前序后序遍历序列之后,可以唯一确定一棵二叉树

44430
  • 二叉树的先遍历遍历 后序遍历遍历

    也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树 二叉树遍历遍历 :先遍历根节点,再遍历左节点,最后遍历右节点 中遍历 :先遍历左节点,再遍历根节点,最后遍历右节点...后序遍历 :先遍历左节点,再遍历右节点,最后遍历根节点 层遍历 : 自上而下,自左至右逐层访问树的结点的过程就是层遍历 遍历方法的实现 先建立一棵树 用代码建立以上树 class Node...this.val = val; } } public class TestTree { public static Node build(){ //手动把一颗树构造出来...= null){ stack.push(top.left); } } } // 二叉树的中遍历,非递归迭代实现...System.out.println(top.val + " "); cur = top.right; } } // 二叉树后序遍历

    1.1K20

    二叉树的先遍历、中遍历后序遍历

    1 问题 Python中二叉树的先遍历、中遍历后序遍历。 2 方法 先遍历的递归算法定义: 若二叉树非空,则依次执行如下操作: ⑴ 访问根结点; ⑵ 遍历左子树; ⑶ 遍历右子树。...中遍历的递归算法定义: 若二叉树非空,则依次执行如下操作: ⑴ 遍历左子树; ⑵ 访问根结点; ⑶ 遍历右子树。...后序遍历的递归算法定义: 若二叉树非空,则依次执行如下操作: ⑴ 遍历左子树;⑵ 遍历右子树;⑶ 访问根结点。...(btree.base) 3 结语 我们针对Python中二叉树的先遍历、中遍历后序遍历的问题,运用书上相应的基础知识,通过代码运行成功证明该方法是有效的,二叉树遍历的应用非常广泛,希望通过未来的学习我们能写出更多长的...、复杂的代码程序。

    17510

    二叉树的先,中,后序遍历的序列_二叉树遍历后序遍历正好相反

    此外,还有一个命题:给定了二叉树的任何一种遍历序列,都无法唯一确定相应的二叉树。但是如果知道了二叉树的中遍历序列任意的另一种遍历序列,就可以唯一地确定二叉树。...例子1:已知二叉树后序遍历序列是dabec,中遍历序列是debac,它的前序遍历序列是(cedba)。...(1)中遍历:debac 后序遍历:dabec 后序遍历序列的最后一个结点是根结点,所以可知c为根结点。 中遍历序列的根结点在中间,其左边是左子树,右边是右子树。...所以从中遍历序列中可看出,根结点c只有左子树,没有 右子树。 (2)中遍历:deba 后序遍历:dabe 后序遍历序列的最后一个结点是根结点,所以可知e为c的左子树的根结点。...(3)中遍历:ba 后序遍历:ab 由后序遍历序列可知b为e的右子树的根结点。由中遍历序列中可看出,a为根结点b的右子结点。

    55420

    根据后序遍历输出先遍历

    本文链接:https://blog.csdn.net/weixin_42449444/article/details/85331082 题目描述: 本题要求根据给定的一棵二叉树后序遍历遍历结果...随后两行,每行给出N个整数,分别对应后序遍历遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。 输出格式: 在一行中输出Preorder:以及该树的先遍历结果。...输入样例: 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 输出样例: Preorder: 4 1 3 2 6 5 7 相关知识: 1.先遍历的递归过程为:若二叉树为空,遍历结束。...否则:①访问根结点;②先遍历根结点的左子树;③先遍历根结点的右子树。 简单来说先遍历就是在深入时遇到结点就访问。 2.中遍历的递归过程为:若二叉树为空,遍历结束。...否则:①中遍历根结点的左子树;②访问根结点;③中遍历根结点的右子树。简单来说中遍历就是从左子树返回时遇到结点就访问。 3.后序遍历的递归过程为:若二叉树为空,遍历结束。

    94610

    二叉树前序遍历、中遍历后序遍历、层遍历的直观理解

    为什么叫前序、后序、中?...一棵二叉树由根结点、左子树右子树三部分组成,若规定 D、L、R 分别代表遍历根结点、遍历左子树、遍历右子树,则二叉树遍历方式有 6 种:DLR、DRL、LDR、LRD、RDL、RLD。...由于先遍历左子树遍历右子树在算法设计上没有本质区别,所以,只讨论三种方式: DLR–前序遍历(根在前,从左往右,一棵树的根永远在左子树前面,左子树又永远在右子树前面 ) LDR–中遍历(根在中,从左往右...中遍历(LDR) 后序遍历(LRD) 2....层遍历遍历嘛,就是按层,从上到下,从左到右遍历,这个没啥好说的。 参考 1.

    2.1K40

    二叉树---(3)前序遍历,中遍历后序遍历

    很多朋友在刚开始接触二叉树时,对前序遍历,中遍历后序遍历这三个遍历方式不太了解,很多博客中,上来就是实现方式,并没有清晰的阐述这三种遍历的步骤和顺序,这里记录一下。        ...遍历二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。         按照根节点位置的不同分为前序遍历,中遍历后序遍历。...前序遍历:根节点->左子树->右子树 中遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 注意:在做前序遍历时,左右子树也是按照前序遍历的顺序, 同理,在做中遍历时,左右子树也是按照中遍历的顺序...例1:求下面树的三种遍历 ? 前序遍历:abdefgc 中遍历:debgfac 后序遍历:edgfbca 例2:求下面树的三种遍历 ?    ...前序遍历:  A B D I J E K L Q C F M N G O P      中遍历 I D J B K E Q L A M F N C O G P      后序遍历   I J

    67720

    给出前序遍历遍历二叉树_已知前序遍历后序遍历

    一、基本概念 1.先遍历(NLR)可以确定二叉树的父子结点; 2.中遍历(LNR)可以确定二叉树的左右子树; 3.后序遍历(LRN)可以确定二叉树的父子结点; 二、结论 1.已知先遍历,中遍历序列...,能够创建出一棵唯一的二叉树,可以得出二叉树后序遍历; 2.已知后序遍历,中遍历序列,能够创建出一棵唯一的二叉树,进而可以得出二叉树的先序列; 3.综上,必须含有中遍历(确定二叉树左右孩子),先遍历或者后序遍历任选一个...(确定二叉树父子结点),就可以确定一棵唯一的二叉树 三、C++代码实现 1.已知先遍历遍历,打印后序遍历(见函数void postorder(string preorder, string inorder...)); 2.已知中遍历后序遍历,打印先遍历(见函数void preorder(string inorder, string postorder)); #include #include...; //最后输出根节点 } void preorder(string inorder, string postorder) //由中遍历+后序遍历序列,递归实现先序列 (NLR) { int

    58620

    从前序与中遍历序列构造二叉树从中后序遍历序列构造二叉树

    题目大意 根据二叉树的前序遍历遍历( 中后序)结果生成二叉树 假设没有重复数字 解题思路 参考给中后序遍历 看到树首先想到要用递归来解题。...以这道题为例:如果一颗二叉树为{1,2,3,4,5,6,7},则中遍历为{4,2,5,1,6,3,7},后序遍历为{4,5,2,6,7,3,1},我们可以反推回去。...根据中遍历的定义,1左边的数{4,2,5}就是左子树的中遍历,1右边的数{6,3,7}就是右子树的中遍历。而对于后序遍历来讲,一定是先后序遍历完左子树,再后序遍历完右子树,最后遍历根。...于是可以推出:{4,5,2}就是左子树的后序遍历,{6,3,7}就是右子树的后序遍历。而我们已经知道{4,2,5}就是左子树的中遍历,{6,3,7}就是右子树的中遍历。...二叉树的前序、中后序遍历(深度优先遍历遍历即将树的所有结点都访问且仅访问一次。

    1.2K20

    树的遍历(已知前序遍历遍历后序遍历,或者已知后序求先)

    假设是1000个结点以内, 输入前序  4 1 3 2 6 5 7        中  1 2 3 4 5 6 7  得到后续  2 3 1 5 7 6 4 已知前序遍历遍历后序遍历: import...,建树 // @param pre 先遍历的数组 // @param lo 先遍历的起点下标 // @param in 中遍历的数组 // @param ini 中遍历的起点下标...ini + i + 1, n - i - 1); // 右区间 // 最后一个参数是这个子树的有多少结点 return node; } } 题目描述 输入某二叉树的前序遍历遍历的结果...,请重建出该二叉树。...假设输入的前序遍历遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

    27820

    前序遍历遍历构造二叉树

    题意 根据前序遍历遍历构造二叉树. 注意事项: 你可以假设树中不存在相同数值的节点 样例 给出中遍历:[1,2,3]前序遍历:[2,1,3]....返回如下的树: 2 / \ 1 3 思路 根据前序遍历遍历的规律可得: 前序遍历的第一个就是整个树的根节点 这个根节点在中遍历的左侧是其左子树,右侧是右子树。...将每一个节点都看作是一个单独的树,根据此 规律1 规律2 依次递归获取其左右子树的前序与中遍历,直到前序遍历或中遍历的长度仅剩1,则说明该节点为叶子节点,从而构造整棵树。...]; //右侧子节点的前序遍历 //从现有的中遍历中拿到 左右子节点的中遍历 for (int i = 0; i < inorder.length; i++) { if...treeRoot.right = buildTree(child_PreorderRight,child_InorderRight); return treeRoot; } } 原题地址 LintCode:前序遍历遍历构造二叉树

    1.8K40

    【LeetCode系列】从中后序遍历序列构造二叉树 & 从前序与中遍历序列构造二叉树

    从前序与中遍历序列构造二叉树 根据一棵树的前序遍历与中遍历构造二叉树。 注意: - 你可以假设树中没有重复的元素。...例如,输入: 前序遍历 preorder = [3,9,20,15,7] 中遍历 inorder = [9,3,15,20,7] 输出:[3,9,20,null,null,15,7] 返回如下的二叉树...从中后序遍历序列构造二叉树 根据一棵树的中遍历后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。...例如,给出 中遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树: 3 / \ 9 20.../ \ 15 7 思路上题类似: 后序遍历是左右根,因此postorder最后一个元素一定是整个树的根。

    46420

    根据先输出后序遍历

    本文链接:https://blog.csdn.net/weixin_42449444/article/details/86178278 题目描述: 二叉树的前序、中后序遍历的定义: 前序遍历:对任一子树...给定一棵二叉树的前序遍历遍历,求其后序遍历(提示:给定前序遍历与中遍历能够唯一确定后序遍历)。 输入描述: 两个字符串,其长度n均小于等于26。 第一行为前序遍历,第二行为中遍历。...否则:①访问根结点;②先遍历根结点的左子树;③先遍历根结点的右子树。 简单来说先遍历就是在深入时遇到结点就访问。 2.中遍历的递归过程为:若二叉树为空,遍历结束。...否则:①中遍历根结点的左子树;②访问根结点;③中遍历根结点的右子树。简单来说中遍历就是从左子树返回时遇到结点就访问。 3.后序遍历的递归过程为:若二叉树为空,遍历结束。...: #include using namespace std; void getpost(string preorder,string inorder) //根据先后序

    2.2K20
    领券