Nc204382 medium sequence

subject ： NC204382 Middle order sequence , ha-ha , Let's look at a classic binary tree problem today , This is a question from Niuke , Okay , Let's have a look at the meaning of the title ：

The title description is copied , There may be some display errors , I'll put the title link below ！
Topic link ： NC204382 Middle order sequence

Be careful : This problem is the core code pattern , It's the submission mode of helikou ！

Title Description

Given a tree with n The sequence of preorder traversal and postorder traversal of a binary tree with nodes , Find the middle order traversal sequence . If a node has only one child node , Then it is regarded as the left son node

Example 1

Input

5,[3,2,1,4,5],[1,5,4,2,3]

Output

[1,2,5,4,3]

Let's look at success AC The code of ：

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:
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * * @param n int  Number of binary tree nodes  * @param pre intvector  Preorder sequence  * @param suf intvector  Subsequent sequence  * @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;
    }
};

Thanks for reading , Because the author level is limited , There are inevitably shortcomings , If the reader finds a problem , Please criticize , Leave a message in the message area or send a private message to inform , I will revise it as soon as possible . If you guys have any good solutions , Or meaningful solutions can be displayed in the comment area , Thank you very much .
Writing is not easy to , I hope all bosses will praise me , Add a focus on !