题目： NC204382 中序序列 ，哈哈，我们今天来看一道经典的二叉树的题嘛，这是选自牛客上的一道题，好了，我们一起来看看题意吧：
题目描述是复制的，可能有部分显示不对，我就把题目链接放下面！
题目链接： NC204382 中序序列
注意 :这道题是核心代码模式，就是和力扣的那种提交模式！
题目描述
给定一棵有n个结点的二叉树的先序遍历与后序遍历序列，求其中序遍历序列。 若某节点只有一个子结点，则此处将其看作左儿子结点
示例1
输入
5,[3,2,1,4,5],[1,5,4,2,3]
输出
[1,2,5,4,3]
我们来看看成功AC的代码吧：
vector<int> v; void dfs(int l1,int r1,int l2,int r2,vector<int>& pre, vector<int>& suf){ // if(l1>r1) return ; if(l1==r1) {v.push_back(pre[l1]); return ;} int pos=-1; int x=pre[l1+1]; for(int i=l2;i<=r2;i++){ if(suf[i]==x) pos=i; } dfs(l1+1,l1+1+pos-l2,l2,pos,pre,suf); v.push_back(pre[l1]); if(pos+1<=r2-1) dfs(l1+1+pos-l2+1,r1,pos+1,r2-1,pre,suf); } class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int 二叉树节点数量 * @param pre intvector 前序序列 * @param suf intvector 后序序列 * @return intvector */ vector<int> solve(int n, vector<int>& pre, vector<int>& suf) { // write code here dfs(0,n-1,0,n-1,pre,suf); return v; } };
