首页 > 其他分享 >已知二叉树的前序和中序遍历求后序遍历

已知二叉树的前序和中序遍历求后序遍历

时间:2024-04-23 18:45:10浏览次数:22  
标签:遍历 int 中序 该数 二叉树 root 前序

假设二叉树上各结点的权值互不相同且都为正整数。

给定二叉树的前序遍历和中序遍历,请你输出二叉树的后序遍历序列。

输入格式

第一行包含整数 N,表示二叉树结点总数。

第二行给出二叉树的前序遍历序列。

第三行给出二叉树的中序遍历序列。

输出格式

输出二叉树的后序遍历的第一个数字。

数据范围

1≤N≤50000

输入样例:

7
1 2 3 4 5 6 7
2 3 1 5 4 7 6

输出样例:

3 2 5 7 6 4 1

已知树的先序遍历的第一个元素就是树(子树)的根节点

手动模拟求后序遍历:

  • 找先序中第一个数,再看该数在中序遍历中的位置
  • 中序位置的左边的数就在该数的左子树上, 右边的数就在该数的右子树上
  • 再看该数的先序中 左子树上的数离该数最近的 和 右子树上的数离该数最近的 , 这两个离得最近得数就是该数的左右子树的根节点

代码解读
代码中的build函数传递的是 先序和后序序列的左右闭区间
找到左右子树的左右闭区间, 每次取先序的第一个数就可以完成上述手动模拟操作,构建出完整的树

先序的左右闭区间不会找的话看下面的图

标签:遍历,int,中序,该数,二叉树,root,前序
From: https://www.cnblogs.com/xxctx/p/18153552

相关文章

  • 已知二叉树的后序和中序遍历求前序遍历
    假设二叉树上各结点的权值互不相同且都为正整数。给定二叉树的后序遍历和中序遍历,请你输出二叉树的前序遍历的最后一个数字。输入格式:第一行包含整数N,表示二叉树结点总数。第二行给出二叉树的后序遍历序列。第三行给出二叉树的中序遍历序列。输出格式输出二叉树的前序遍......
  • 二叉树深度的题目
    #这是一道关于二叉树深度的题目。题目要求我们输入一个二叉树的结点数和每个结点的左右子结点编号,然后输出这棵二叉树的最大深度。#对于这个问题,我们可以使用递归的方法来求解。以下是一个Python的代码示例: depth=1defdfs(node,depth):ifnode==0:retu......
  • 单向链表的插入删除和遍历
    /*********************************************************************************************************** FileName:LinkedList * Author:madman_LX*Contactme:[email protected]* Date :2024/04/22* Function:单向链表的遍历,插......
  • JZ8 二叉树的下一个结点
    #include<cstddef>classSolution{public:vector<TreeLinkNode*>nodes;//用户得到的输入只有一个子树根节点TreeLinkNode*GetNext(TreeLinkNode*pNode){TreeLinkNode*root=pNode;//获取根节点 //顺着next指针一直......
  • JZ79 判断是不是平衡二叉树
    classSolution{public://求深度intdeep(TreeNode*root){if(root==NULL)return0;//求左右子树的深度intleft=deep(root->left);intright=deep(root->right);return......
  • 单向链表遍历插入和删除
    /***********************************************************************************filename:002_单向链表.cauthor:[email protected]:2024/04/22function:单向链表的遍历插入和删除功能的完善note......
  • 【二叉树的前中后序遍历】迭代法
    三种遍历都是用栈维护二叉树前序遍历节点顺序前序遍历模拟前序遍历即可,记录顺序和入栈顺序一致classSolution{publicList<Integer>preorderTraversal(TreeNoderoot){List<Integer>ans=newArrayList<>();if(root==null)returnans;......
  • JZ86 在二叉树中找到两个节点的最近公共祖先
    classSolution{public://用来判断是否找到节点boolflag=false;//dfs遍历得到路径,递归遍历,也就是先序遍历根左右//传入参数:节点,容器,要找的值voiddfs(TreeNode*root,vector<int>&path,into){//判断根节点的值是否是要找的......
  • 【根据前序和中序遍历构造二叉树】栈+迭代 || 递归
    105.从前序与中序遍历序列构造二叉树栈+迭代规律前序遍历中相邻节点u和v,v节点一定是u节点的左节点或者是其自身某个祖先的右节点一个没有右节点的链,中序遍历是从叶子到根,前序遍历是从根到叶子解题思路用一个栈维护前序遍历的节点用一个指针p指向中序遍历的第一个叶子节......
  • 给出二叉树的前序遍历和中序遍历--还原二叉树
    voidf(intidxroot){ //根据前序遍历和中序遍历还原二叉树if(idxroot==n+1)return;introot=pre[idxroot];boolcheck=true;map<int,int>lcmp,rcmp;//当前节点的左孩子集合和右孩子集合for(inti=1;i<=n;i++){if(vis[mid[i]]&&mid[i]!......