1589. 构建二叉搜索树------------》l[],r[]建树

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int pos[N];//数值映射

int f[N],l[N],r[N];
int cnt[N];
int ma_depth;
void dfs(int root,int x,int depth){
    int b=pos[root];
    int e=pos[x];
      ma_depth=max(ma_depth,depth+1);
    if(b>=e){
        if(l[root]==0x3f3f3f3f){
            l[root]=x;


            cnt[depth+1]++;//必须遍历到叶子节点才能确定其所在的层数
        }
        else{
            dfs(l[root],x,depth+1);
        }
    }
    else if(b<e){
        if(r[root]==0x3f3f3f3f){
            r[root]=x;

             cnt[depth+1]++;
        }
        else{
             dfs(r[root],x,depth+1);
        }
    }
}
int main(){
    int n;
    cin>>n;
    memset(l,0x3f,sizeof l);
    memset(r,0x3f,sizeof r);
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        pos[i]=x;
        dfs(0,i,0);//从第0层开始遍历

    }

    printf("%d + %d = %d",cnt[ma_depth],cnt[ma_depth-1],cnt[ma_depth]+cnt[ma_depth-1]);
    return 0;
}

1527. 判断二叉搜索树-------》前序中序建树

//二叉搜索树，中序遍历非递减
//其镜像，中序遍历非递增
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1010;
int pre[N],in[N];
int l[N],r[N];
int init(int pl,int pr,int il,int ir){
    if(il>ir){//-------------------------->表示建树成功
        return 1;
    }
    int root=pre[pl];
    //中序：根左右
    int order;
    int flag=0;
    for(int i=il;i<=ir;i++){-------------->因为树中有重复的编号，所以需要这样遍历
    如果是镜像应该从后向前遍历
        if(in[i]==root){
            order=i;
            flag=1;

            break;
        }
    }

   if(!flag){
       return 0;
   }

        if(!init(pl+1,pl+order-il,il,order-1))
        return 0;
        if(!init(pr-ir+order+1,pr,order+1,ir))
        return 0;
    cout<<root<<' ';
    return 1;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        pre[i]=x;
        in[i]=x;
    }
    sort(in,in+n);
    int root=init(0,n-1,0,n-1);
    cout<<endl;
    if(root){
        printf("Yes");
    }
    return 0;
}

1550. 完全二叉搜索树-------->数组建树

//完全二叉树的中序遍历是依次递增的-----------------》
本题目树节点的下标和节点编号是不同的
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=2005;
int a[N],b[N];
int k=0;
int n;
void dfs(int root){
    if(2*root<=n){
        dfs(2*root);
    }
    b[root]=a[k++];
    if(2*root+1<=n){
        dfs(2*root+1);
    }
}
vector<int>ans;
void bfs(int u){

    queue<int>res;
    res.push(u);//存储节点的下标
    ans.push_back(b[u]);
    while(!res.empty()){

        int si=res.size();
        for(int i=0;i<si;i++){
            int x=res.front();
             res.pop();
        if(2*x<=n){
            res.push(2*x);
            ans.push_back(b[2*x]);
        }
        if(2*x+1<=n){
            res.push(2*x+1);
            ans.push_back(b[2*x+1]);
        }
        }

    }
    for(auto &t:ans){
        cout<<t<<' ';
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    dfs(1);//根节点的下标为1
    bfs(1);
    return 0;
}

最低公共祖先-----------------》思路！！！

//在构建二叉树的时候数组中下标为当前节点的权值，元素值为其父节点
#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=10010;
unordered_map<int,int>p,order,d,pre,in,l,r,st;
  int build(int il,int ir,int pl,int pr,int depth){
      int root=pre[pl];
      int index=order[root];
      d[root]=depth;
      if(il<index){
          //其左子节点存在
          p[build(il,index-1,pl+1,pl+index-il,depth+1)]=root;

      }
      if(index<ir){

         p[build(index+1,ir,pl+index-il+1,pr,depth+1)]=root;
      }
   return root;   
  }
  int g;
  /*void dfs(int root){-------------------->不可行，因为节点编号在int范围内
  if(st[root]==-1){
      return ;

  }
  if(l[root]){
      p[l[root]]=root;
      dfs(l[root]);
  }
  if(r[root]){
      p[r[root]]=root;
      dfs(r[root]);
  }
  }*/
int main(){

    int m,n;
    cin>>m>>n;

    unordered_set<int>res;
            int x;
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        st[x]=1;
        in[i]=x;
        order[x]=i;
        res.insert(x);
    }
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        pre[i]=x;
        res.insert(x);
    }
   int root=build(0,n-1,0,n-1,0);
    int mi=m-1;
    //dfs(root);
    while(m--){
        int l,r;
        cin>>l>>r;
        if(m!=mi){
            printf("\n");
        }
        int a=l,b=r;
        if(res.count(l)&&res.count(r)){
           while(l!=r){//------------------>灵魂！！
               if(d[l]<d[r]){
                   r=p[r];
               }
               else{
                   l=p[l];
               }
           }


            if(a!=l&&b!=r){
                printf("LCA of %d and %d is %d.",a,b,l);

            }
            else if(a==l){
                printf("%d is an ancestor of %d.",a,b);
            }
            else{
                 printf("%d is an ancestor of %d.",b,a);
            }
        }
        else if(!res.count(l)&&!res.count(r)){
           printf("ERROR: %d and %d are not found.",l,r);
        }
        else if(!res.count(l)){
            printf("ERROR: %d is not found.",l);
        }
        else{
            printf("ERROR: %d is not found.",r);
        }

    }
    return 0;
}

1539. 等重路径----------->DFS 中存在细节问题，细节决定成败

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int h[N],e[N],ne[N];
int idx;
int w[N];
void init(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
vector<vector<int>>res;
int n,m,we;
int k;
void dfs(int root,int sum,vector<int> &temp){

    if(h[root]==-1){

     if(we==sum){
      res.push_back(temp);


     }
     return ;   
    }

    for(int i=h[root];i!=-1;i=ne[i]){
        int j=e[i];
        temp.push_back(w[j]);
        dfs(j,sum+w[j],temp);
        temp.pop_back();//-------------->这个地方忽略

    }
}
int main(){

    cin>>n>>m>>we;
    memset(h,-1,sizeof h);
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    for(int i=0;i<m;i++){
        int x,si;
        cin>>x>>si;
        for(int j=0;j<si;j++){
            int y;
            cin>>y;
            init(x,y);
        }
    }
    vector<int>temp;
    temp.push_back(w[0]);
    int x;
    dfs(0,w[0],temp);
    sort(res.begin(),res.end(),greater<vector<int>>());

    for(auto &t:res){
        for(auto &tt:t){
            cout<<tt<<' ';
        }
        cout<<endl;
    }
    return 0;
}

1649. 堆路径

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int h[N];
int tree[N];
int k=2;
int n;
void init(int u){
    if(2*u>n)
    return ;
    if(2*u<=n){
        tree[2*u]=h[k++];
    }
    init(2*u);
    if(2*u+1<=n){
        tree[2*u+1]=h[k++];
    }
    init(2*u+1);
}
vector<vector<int>>path;
int flag=0;
int thi;
void dfs(int root,vector<int> &temp,int &type){
    //temp存储节点的下标
       if(2*root>n){
        path.push_back(temp);
        return ;
    }
     int t=type;

     if(2*root+1<=n){
        temp.push_back(2*root+1);
        if(tree[2*root+1]>tree[root]){
            type=1;
        }
       else if(tree[2*root+1]<tree[root]){
            type=0;
        }
        else
        type=t;
         thi=type;
         if(type^t&&root!=1){
            flag=1;
        }

        dfs(2*root+1,temp,type);
        temp.pop_back();
    }
    if(2*root<=n){
        temp.push_back(2*root);

        if(tree[2*root]>tree[root]){
            type=1;
        }
        else if(tree[2*root]<tree[root]){
            type=0;
        }
        else
        type=t;
        if(type^t&&root!=1){
            flag=1;
        }
        dfs(2*root,temp,type);
        temp.pop_back();
    }
}
int main(){

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>tree[i];
    }
    //tree[1]=h[1];
   // init(1);
    vector<int>temp;
    int type;
    temp.push_back(1);
    dfs(1,temp,type);
    for(auto &t:path){
        for(auto &tt:t){
            cout<<tree[tt]<<' ';
        }
        cout<<endl;
    }
    if(flag){
        cout<<"Not Heap"<<endl;
    }
    else if(thi==0){
        cout<<"Max Heap"<<endl;
    }
    else{
        cout<<"Min Heap"<<endl;
    }

    return 0;
}

团伙头目！！！！