#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<queue>
using namespace std;

const int N=30+10;

//记录中序遍历的点
vector<int>inorder(N,0);    
//记录后序遍历的点
vector<int>postorder(N,0);  
//记录中序遍历序列每个点的相应位置 第一维表示值 第二维其在中序序列中的具体位置
unordered_map<int,int>pos;
//记录原本的树的信息 第一维为表示树结点的值 第二维表示树节点指向的节点
unordered_map<int,int>l,r;  


//返回值为当前所在节点区间的根
int build(int il,int ir,int pl,int pr){
    int root=postorder[pr];
    int k=pos[root];


    //存在左子树
    if(il<k)
        l[root]=build(il,k-1,pl,pl+(k-1)-il);
    //存在右子树
    if(ir>k)
        r[root]=build(k+1,ir,pl+(k-1-il)+1,pr-1);

    /**
    * 关于递归的区间划分问题
    * 很显然递归的目的是进入左右然后再次寻找根
    * 所以对于中序遍历很简单结合数轴就可以理解
    * 因为k为根节点的位置 所以k左右两边左右子树即对应(il,k-1)(k+1,ir)
    * 而对于后序遍历则稍微要绕一下
    * 由于后序遍历区间的节点数与中序遍历是相等的(这是因为每次划分都是以后序树确定的根为依据)
    * 所以每次划分后 后序树的左右树也会有与中序树相对应的区间范围
    * 即(pl,pl+(k-1)-il)(pl+(k-1-il)+1,pr-1)
    */
    return root;
}

void bfs(int root){
    queue<int>q;
    q.push(root);
    cout<<root;
    while(q.size()){
        int t = q.front();
        if(t!=root)
        cout<<' '<<t;
        q.pop();
        if(l.count(t))
            q.push(l[t]);
        if(r.count(t))
            q.push(r[t]);
    }
}


int main(){
    int n;

    cin>>n;

    for(int i=0;i<n;i++)
        cin>>postorder[i];

    for(int i=0;i<n;i++){
        cin>>inorder[i];
        pos[inorder[i]]=i;
    }

    int root=build(0,n-1,0,n-1);

    bfs(root);

    return 0;
}

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res;
        if (strs.empty()) return res;

        for (int i = 0;; i ++ ) {
            if (i >= strs[0].size()) return res;
            char c = strs[0][i];
            int flag=1;
            for (auto& str: strs){
                if (i< str.size()&&str[i] == c)
                    flag=1;
                    else{
                    flag=0;
                    break;
                    }
            }
            if(flag==0)return res;
            else res+=c;
        }

        return res;
    }
};

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res;
        if (strs.empty()) return res;

        for (int i = 0;; i ++ ) {
            if (i >= strs[0].size()) return res;
            char c = strs[0][i];
            int flag=1;
            for (auto& str: strs){
                if (i< str.size()&&str[i] == c)
                    flag=1;
                    else{
                    flag=0;
                    break;
                    }
            }
            if(flag==0)return res;
            else res+=c;
        }

        return res;
    }
};

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> hash;
        hash['I'] = 1, hash['V'] = 5;
        hash['X'] = 10, hash['L'] = 50;
        hash['C'] = 100, hash['D'] = 500;
        hash['M'] = 1000;

        int res = 0;
        for (int i = 0; i < s.size(); i ++ ) {
            if (i + 1 < s.size() && hash[s[i]] < hash[s[i + 1]])
                res -= hash[s[i]];
            else
                res += hash[s[i]];
        }

        return res;
    }
};

class Solution {
public:
    string intToRoman(int num) {
        int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string reps[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        string res;
        for (int i = 0; i < 13; i ++ )
            while(num >= values[i])
            {
                num -= values[i];
                res += reps[i];
            }
        return res;
    }
};

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, m;
vector<int>v[110];
int cnt[110], max_depth;//记录每层叶子结点个数和最大深度
int high[110];//记录每个节点的深度
void bfs(int u)
{
    queue<int>q;
    q.push(u);
    high[u]=0;
    while(q.size()){
        int top=q.front();
        q.pop();
        if (v[top].size() == 0)  // 说明u是叶子节点
        {
        cnt[high[top]] ++ ;
        continue;
      }
    for (int i = 0; i<v[top].size(); i++){
        int e=v[top][i];
        high[e]=high[top]+1;
        max_depth = max(max_depth,high[e]);
        q.push(e);
      }
   }
}


int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int id, k;
        cin >> id >> k;
        while (k -- )
        {
            int son;
            cin >> son;
            v[id].push_back(son);
        }
    }

    bfs(1);
    cout << cnt[0];
    for (int i = 1; i <= max_depth; i ++ ) cout << ' ' << cnt[i];
    cout << endl;

    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, m;
vector<int>v[110];
int cnt[110], max_depth;//记录每层叶子结点个数和最大深度
int high[110];//记录每个节点的深度
void bfs(int u)
{
    queue<int>q;
    q.push(u);
    high[u]=0;
    while(q.size()){
        int top=q.front();
        q.pop();
        if (v[top].size() == 0)  // 说明u是叶子节点
        {
        cnt[high[top]] ++ ;
        continue;
      }
    for (int i = 0; i<v[top].size(); i++){
        int e=v[top][i];
        high[e]=high[top]+1;
        max_depth = max(max_depth,high[e]);
        q.push(e);
      }
   }
}


int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int id, k;
        cin >> id >> k;
        while (k -- )
        {
            int son;
            cin >> son;
            v[id].push_back(son);
        }
    }

    bfs(1);
    cout << cnt[0];
    for (int i = 1; i <= max_depth; i ++ ) cout << ' ' << cnt[i];
    cout << endl;

    return 0;
}

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int p[N];

int find(int x) // 返回x的祖宗节点 + 路径压缩
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    while (m -- )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);

        if (op[0] == 'M') p[find(a)] = find(b);
        else
        {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int head, e[N], ne[N], idx;

void init()
{
    head = -1;
}

void add_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++ ;
}

void add_k(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    init();

    int m;
    cin >> m;
    while (m -- )
    {
        char op;
        int k, x;
        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_head(x);
        }
        else if (op == 'I')
        {
            cin >> k >> x;
            add_k(k - 1, x);
        }
        else
        {
            cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

双指针法

在暴力解法中，每固定一条直线，就要遍历剩下的所有直线，造成了大量元素的多次重复访问。那么我们有没有办法只扫描一次数组，就可以找到最大的面积呢？让我们来看看双指针算法是怎么做的。
最开始的时候，如果我们用指针i和j指向最两端的直线，此时两条直线之间的距离就是最大的，即我们所求矩形面积的宽度(width)为最大。
但是位于最两端的直线不一定是最高的，所以它们组成矩形的面积也就不一定是最大的。因此我们依然需要继续遍历整个数组，这时我们将指向数组两端的指针慢慢往里面收敛，直到找到面积最大值。
对于此时i和j指向的直线，他们之间的宽度已经是最宽了。于是在收敛的过程中，如果遇到的高度比两端的柱子更低的话，由于之间的宽度更短，所以面积必定更小，我们就可以直接跳过，不予考虑。我们只需要考虑收敛时出现的那些高度更高的柱子。
该方法在双指针向中间收敛的过程中，对数组中的每个元素只访问了一次，因此时间复杂度为O(n).
C ++代码
class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1;
        int res = 0;
        while (i < j)
        {
            int h = min(height[i], height[j]);
            res = max(res, h * (j - i));
            while (i < j && height[i] <= h) i ++;
            while (i < j && height[j] <= h) j --;
        }
        return res;
    }
};