天梯赛(GPLT/CCCC)二叉树

已知：节点个数 中序遍历 后序遍历

所求：层序遍历

解法:

中序遍历分左右 后序遍历找树根

后序遍历逆序 "左右根"变为"根右左"

因为"根"很重要 我们优先找根 进行分左右操作

#include
#include
#include
#include
using namespace std;
const int N=40;
queueq;//BFS输出层序遍历时用到的队列
vectorans;//存层序遍历的输出
int a[N];//存后序遍历
int b[N];//存中序遍历
int idx;
int n;

struct Node
{
    int l,r;
}nodes[N];

int build(int L,int R)
{
    if(L>R)return 0;
    int root=++idx;//对应"根右左"中"根"的赋值
    
    //mid寻找该层(L~R)区间的根节点
    int mid;
    for(mid=L;mid<=R;mid++)if(b[mid]==a[idx])break;
    //build函数依照a数组的"根右左"顺序建树
    //下两行命令对应"根右左"中的"右左"
    nodes[root].r=build(mid+1,R);
    nodes[root].l=build(L,mid-1);
    
    return root;
}

void bfs(int x)
{
    q.push(x);
    
    while(q.size())
    {
        int t=q.front();
        q.pop();
        
        //空节点的idx编号为0
        if(t==0)continue;
        
        ans.push_back(t);
        //层序遍历
        //依次把左右子节点放入队列
        q.push(nodes[t].l);
        q.push(nodes[t].r);
    }
}

int main()
{
    cin>>n;
    //后序遍历是"左右根"的顺序
    //逆序读入是获得"根右左"的特殊顺序
    for(int i=n;i>=1;i--)cin>>a[i];//根右左
    for(int i=1;i<=n;i++)cin>>b[i];//中序
    
    //root获得树根的idx值
    //若root为0则为空树
    //否则root=1作为树根
    int root=build(1,n);//建树操作
    
    //层序遍历
    bfs(root);
    
    int si=ans.size();
    int cnt=0;
    for(auto it:ans)
    {
        cout<

已知：前序遍历 中序遍历

所求：镜像翻转后的层序遍历

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

解决镜像问题：交换所有节点的左右子节点 或者 BFS层序遍历时遵循"先右后左"的方式入队

#include
#include
#include
using namespace std;
const int N=40;
vectorans;
int a[N],b[N];
//叶节点的两个空子节点(idx=0)也会入队
//所以数组模拟的队列要开大些
int q[N*N];
int idx;
int n;

struct Node
{
    int l,r;
}nodes[N];

int build(int L,int R)
{
    if(L>R)return 0;
    int root=++idx;//新的根 从1开始
    int mid;//mid是idx编号
    //在中序遍历中寻找与当前子树根节点值相同的节点编号
    //进行"分左右"的操作
    for(mid=L;mid<=R;mid++)if(a[mid]==b[root])break;
    nodes[root].l=build(L,mid-1);
    nodes[root].r=build(mid+1,R);
    
    return root;  
}

void bfs(int s)
{
    int hh=0,tt=0;
    q[0]=s;
    
    while(hh<=tt)
    {
        int t=q[hh++];
        if(t==0)continue;
        ans.push_back(t);
        q[++tt]=nodes[t].r;
        q[++tt]=nodes[t].l;
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];//中序
    for(int i=1;i<=n;i++)cin>>b[i];//前序
    
    int root=build(1,n);
    //for(int i=1;i<=idx;i++)swap(nodes[i].l,nodes[i].r);
    
    bfs(root);
    
    int cnt=0;
    int si=ans.size();
    for(auto it:ans)
    {
        cout< 
 
PTA L2-004 这是二叉搜索树吗？ 
已知：满足二叉搜索树 前序遍历
 
所求：后序遍历
 
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树，对于任一结点：
 
其左子树中所有结点的键值小于该结点的键值；其右子树中所有结点的键值大于等于该结点的键值；其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
 
解决镜像问题：二叉搜索树镜像后 左子树大 右子树小
 
重点思路：
 
在前序或后序遍历中
 
除了第一个或最后一个节点(根节点)
 
其余节点具有"二段性" 对于其中某一段 要么全部大于根节点 要么全部小于根节点
 
若不符合 则该二叉搜索树不合法
 
#include
#include
#include
#include
using namespace std;
const int N=1e5;
vectorans;
int a[N],b[N];
int n,idx,k;
bool flag=true;

struct Node
{
    int l,r,val;
}nodes[N];

//正常建树
int build(int L,int R)
{
    if(!flag)return 0;
    if(L>R)return 0;
    int root=++idx;
    nodes[root].val=a[L];
    int mid=L+1;
    //在区间范围内寻找第一个大于等于根节点的值的位置 存为mid
    //若在mid之后仍然有小于根节点值的值 则非法
    while(a[mid]R)return 0;
    int root=++idx;
    nodes[root].val=a[L];
    if(L==R)return root;
    int mid=L+1;
    while(a[mid]>=a[L]&&mid<=R)mid++;
    //二叉搜索树镜像后
    //左子树大 右子树小
    for(int i=mid;i<=R;i++)if(a[i]>=a[L]){flag=false;return root;}
    nodes[root].l=build2(L+1,mid-1);
    nodes[root].r=build2(mid,R);
    return root;
}

void df(int root)
{
    if(!root)return;
    //后序遍历的输出(放入vector)
    //符合"左右根"
    df(nodes[root].l);
    df(nodes[root].r);
    ans.push_back(root);
}

void dfs(int x)
{
    df(x);
    puts("YES");
    int cnt=0;
    int si=ans.size();
    for(auto it:ans)
    {
        cout<>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    
    int root=build(1,n);
    
    if(flag){dfs(root);return 0;}
    
    flag=true;
    root=build2(1,n);
    if(flag){dfs(root);return 0;}
    
    puts("NO");
    
    return 0;
}
 
PTA L3-016 二叉搜索树的结构 
维护节点所在层数与父节点
 
已知：一堆节点的值
 
方法：使用insert函数建立二叉搜索树
 
#include
#include
#include
#include
 
PTA L2-035 完全二叉树的层序遍历 
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是完美二叉树。
 
完全二叉树：如果不完美 最后一层的节点全部"靠左" 最后一层以上全满
 
已知：完全二叉树的后序遍历
 
所求：层序遍历
 
当用"x<<1"与"x<<1|1"表示左右子节点的编号建树时
顺序遍历数组就是层序遍历 不需要BFS
 
#include
#include
#include
#define lc (x<<1)
#define rc (x<<1|1)
using namespace std;
const int N=1e4;
int val[N];
int n;
void build(int x)
{
    //由后序遍历建树
    //依照"左右根"的顺序
    if(lc<=n)build(lc);//左
    if(rc<=n)build(rc);//右
    cin>>val[x];//根
}

void bfs(int x)
{
    queueq;
    q.push(x);
    int cnt=0;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        cout<>n;
    build(1);
    //bfs(1);
    //当用x<<1 x<<1|1 表示左右子节点时
    //顺序遍历数组就是层序遍历 不需要bfs
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        cout< 
PTA L3-010 是否完全二叉搜索树 
本题的特殊定义 二叉搜索树中 (左子树键值大 右子树键值小)
 
题意：按照二叉搜索树的要求插入节点 判断是否是完全二叉树 并给出层序遍历
 
判断技巧：
 
如果有一个节点的idx编号超过节点数
 
一定是不完全的
 
可以理解为前面少了一个节点补到的后面 如果全满就不会有超过n(节点数)的编号
 
#include
#include
#include
using namespace std;
const int N=4e5;
struct Node
{
    //记录数值 二叉树中的编号
    //符合x<<1 x<<1|1 的规则
    int l,r,val,id;  
}nodes[N];
int n;
int idx;
int id;
//pos是引用传参
void insert(int& pos,int val)
{
    //当pos为0时 说明找到了可以插入的位置
    //叶子节点的左右子节点的idx编号值为0
    if(pos==0)
    {
        pos=++idx;
        nodes[pos].val=val;
        nodes[pos].id=id;
        return;
    }
    if(val>nodes[pos].val)
    {
        id=id*2;
        insert(nodes[pos].l,val);
    }
    else
    {   
        id=id*2+1;
        insert(nodes[pos].r,val);
    }
}
int main()
{
    int root=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int tmp;cin>>tmp;
        //每次插入id从1开始
        //往左*2 往右*2+1
        id=1;
        insert(root,tmp);
    }
    queueq;
    q.push(root);
    bool flag=true;
    int cnt=0;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        if(!t)continue;
        //如果idx值大于总节点数 一定不合法
        if(nodes[t].id>n)flag=false;
        cout<