当前位置：首页 > news >正文

L2-006 数的遍历（递归经典，图论）

news 2026/3/27 5:56:08

题目描述

给出二叉树后序遍历和中序遍历，请你输出它的前序遍历，这里假设键值都是互不相等的正整数。

输入示例

第一行给出一个正整数n，第二行给出后序遍历，第三行给出中序遍历

输出示例

输出前序遍历 O(∩_∩)O 。

解题思路

虽然柳婼大大说这题不用建树，但是我就要建┗|｀O′|┛

递归建树 + BFS ：

对于一个一般的二叉树，我们只有联立中序 + 前（后）序才能建树，我们要先从中序中找到根节点（后序的最后一个数在哪个位置）
找到根后，中序遍历被分为两半，我们可以找到相对应的区间进行建树，如图：

假设根在 中序遍历 中的下标为 \(k\) , 那么左子树的节点个数为：numleft = k - il (去掉根) , 那么左子树对应的建树区间就是：后序[pr , pr + (numleft-1)] 中序[il,k-1] 。右子树对应的建树区间就是: 后序[pr + numleft] ，中序[k,ir]

递归结束后返回root

3.BFS遍历输出层序遍历
需要用一个res数组来存层序遍历结果

ac✅️代码

#include<iostream>
#include<queue>
#include<unordered_map>
#include<vector>
using namespace std;
int post[35],in[35];
unordered_map<int,int> l,r,pos;//il是中序区间的左边界，ir是右边界；
int build(int pl,int pr,int il,int ir)
{if(pl>pr) return 0;int root = post[pr];int k = pos[root];int numleft = k - il;//这里的post区间与in区间是对应的，可以画个图。l[root] = build(pl,pl + (numleft - 1) , il , k - 1);//中序右区间右边界不变r[root] = build(pl + numleft,pr-1,k+1,ir);return root;//这里不要o(>﹏<)o去想后序的递归过程专心于第一次就行，不然会很麻烦
}void levelOrder(int startNode)
{vector<int> res;queue<int> q;q.push(startNode);while(!q.empty()){int curr = q.front();q.pop();if(curr == 0) continue;res.push_back(curr);if(l[curr] != 0) q.push(l[curr]);if(r[curr] != 0) q.push(r[curr]);	}for(int i = 0 ; i < res.size() ; i++){cout<<res[i];if(i != res.size() - 1) cout<<" ";}
}int main()
{int n;cin>>n;for(int i = 0 ; i < n ; i++) cin>>post[i];for(int i = 0 ; i < n ; i++) {cin>>in[i];pos[in[i]] = i ;}int root = build( 0 , n - 1 , 0 , n -1 );levelOrder(root);return 0;}