NC204382 中序序列-蒲公英云

NC204382 中序序列

⭐简单说两句⭐

作者：**后端小知识**

CSDN个人主页：后端小知识

?GZH：后端小知识

?欢迎关注?点赞?收藏⭐️留言?

题目： 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;
    }
};