【题解】牛牛的完全二叉树

题意

给你一个完全二叉树，可以进行两种操作

• 1 x，对编号为x节点的值与其左右儿子进行排序，使结果为父左儿子右儿子
• 2 x，按顺序输出第x层节点的值

题解

直接用链表构建二叉树的话是不方便直接访问节点的。所以我们可以用数组进行构建二叉树。数组下标即二叉树节点编号，节点编号为x的节点，其左儿子为2x，右儿子为2x+1。由于给定的节点值是以层次遍历的给的，所以在数组中也就可以一一对应。交换时注意只有一个儿子的节点以及叶子节点是不需要交换的，还有获取左右儿子时编号得乘二注意数组越界。那么第x层元素的编号应为1<<(x-1)至(1<<x)-1。按顺序直接输出即可。

复杂度

时间复杂度为
空间复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N];
int main()
{

    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    while(m--)
    {
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1)
        {
            vector<int>b;
            if(a[x]!=0)
            b.push_back(a[x]);
            if(2*x<=n&&a[2*x]!=0)
            b.push_back(a[2*x]);
            if(2*x+1<=n&&a[2*x+1]!=0)
            b.push_back(a[2*x+1]);
            sort(b.begin(),b.end());
            if(b.size()==3)
            {
                a[x]=b[2];
                a[2*x]=b[1];
                a[2*x+1]=b[0];
            }
            else if(b.size()==2)
            {
                a[x]=b[1];
                a[2*x]=b[0];
            }
        }
        else
        {
            for(int i=(1<<(x-1));i<(1<<x)&&i<=n;i++)
            {
                if(i!=((1<<x)-1)&&i!=n)
                    printf("%d ",a[i]);
                else
                    printf("%d\n",a[i]);
            }
        }
    }
    return 0;
}