NC204382 中序序列

骑猪看日落 2024-04-20 07:13 56阅读 0赞

⭐**简单说两句**⭐

> **作者：****后端小知识**
> 
> **CSDN**个人主页：[后端小知识][Link 1]
> 
> ?**GZH**：`后端小知识`
> 
> ?欢迎关注?点赞?收藏⭐️留言?

题目： NC204382 中序序列  ，哈哈，我们今天来看一道经典的二叉树的题嘛，这是选自牛客上的一道题，好了，我们一起来看看题意吧：

题目描述是复制的，可能有部分显示不对，我就把题目链接放下面！  
题目链接： [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;
        }
    };

【都看到这了，点点赞点点关注呗，爱你们】??

![抽象工厂  引导关注][1caaf89f43f9c2ec5fdddccc50c08a6c.png]

**结语**

`谢谢你的阅读`，由于作者水平有限，难免有不足之处，若读者发现问题，还请批评，在留言区留言或者私信告知，我一定会尽快修改的。若各位大佬有什么好的解法，或者有意义的解法都可以在评论区展示额，万分谢谢。  
写作不易，望各位老板点点赞，加个关注!???

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

**CSDN**个人主页：[后端小知识][Link 1]

?**GZH**：`后端小知识`

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

[Link 1]: https://blog.csdn.net/m0_46833224
[NC204382]: https://ac.nowcoder.com/acm/problem/204382
[1caaf89f43f9c2ec5fdddccc50c08a6c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/6f7bc22ce6bc4c23a2ec69a4d18dfb72.png