BST和一些树的遍历题目

  1 //代码量较大的一道题，但还是考的BST的基本操作
  2 //这道题要求判断原始序列是同先序序列相同还是与镜像先序序列相同，所谓镜像就是交换左右子树，只要在遍历的时候
  3 //先遍历右子树在遍历左子树就可以解决这个问题了
  4 //需要注意的一点是在插入的时候如果插入键值x小于节点的键值，就插入，注意，是严格小于，没有等号
  5 #include<bits/stdc++.h>
  6 using namespace std;
  7 #define int long long 
  8 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  9 const int N=1e3+10;
 10 struct node
 11 {
 12     int data;
 13     node *l;
 14     node *r;
 15     node(int data=0,node *l=NULL,node *r=NULL):data(data),l(l),r(r){}
 16 };
 17 int n;
 18 vector<int>ori,pre,prem,post,postm;
 19 void insert(node *&root,int x)
 20 {
 21     if(root==NULL)
 22     {
 23         root=new node;
 24         root->data=x;
 25         root->l=root->r=NULL;
 26         return ;
 27     }
 28     if(root->data>x)//不是大于等于，是严格大于
 29     {
 30         insert(root->l,x);
 31     }
 32     else{
 33         insert(root->r,x);
 34     }
 35 }
 36 void build_tree(node *&root)
 37 {
 38     int tmp;
 39     for(int i=0;i<n;i++)
 40     {
 41         cin>>tmp;
 42         ori.push_back(tmp);
 43         insert(root,tmp);
 44     }
 45 }
 46 void preorder(node *&root)
 47 {
 48         if(root!=NULL)
 49         {
 50             pre.push_back(root->data);
 51             preorder(root->l);
 52             preorder(root->r);
 53         }
 54 }
 55 void preorderm(node *&root)
 56 {
 57     if(root!=NULL)
 58     {
 59         prem.push_back(root->data);
 60         preorderm(root->r);
 61         preorderm(root->l);
 62     }
 63 }
 64 void postorder(node *&root)
 65 {
 66     if(root!=NULL)
 67     {
 68         postorder(root->l);
 69         postorder(root->r);
 70         post.push_back(root->data);
 71     }
 72 }
 73 void postorderm(node *&root)
 74 {
 75     if(root!=NULL)
 76     {
 77         postorderm(root->r);
 78         postorderm(root->l);
 79         postm.push_back(root->data);
 80     }
 81 }
 82 signed main()
 83 {
 84     IOS;
 85     cin>>n;
 86     node *root=NULL;
 87     build_tree(root);
 88     preorder(root);
 89     preorderm(root);
 90     postorder(root);
 91     postorderm(root);
 92     if(ori==pre)
 93     {
 94            cout<<"YES"<<endl;
 95         for(int i=0;i<post.size();i++)
 96         {
 97             cout<<post[i];
 98             if(i<post.size()-1)
 99                 cout<<" ";
100         }
101     }
102     else if(ori==prem)
103     {
104         cout<<"YES"<<endl;
105         for(int i=0;i<postm.size();i++)
106         {
107             cout<<postm[i];
108             if(i<postm.size()-1)
109                 cout<<" ";
110         }
111     }
112     else{
113         cout<<"NO";
114     }
115     return 0;
116 }

  1 //比较难做的树类题
  2 //其中思想是很清晰的，就是根据后中序来确定层序，并且层序的输出是一个Z形的输出
  3 //根据后中序确定一棵树就不说了，来说一说这里不同的bfs
  4 //根据题意要设置一个lay来表示深度，设初始深度为1，且每深入一层就加一层，并且在深入中不断去求最大深度
  5 //对于如何储存层序序列，可以设一个二维数组，第一维度来表示深度，第二维度表示序列是几
  6 //之后根据奇偶性质来输出层序序列
  7 //代码较为繁琐，但思路其实是很清晰的
  8 #include<bits/stdc++.h>
  9 using namespace std;
 10 #define int long long 
 11 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 12 const int N=40;
 13 struct node
 14 {
 15     int data;
 16     node *r;
 17     node *l;
 18     int lay;
 19     node(int data=0,node *l=NULL,node *r=NULL,int lay=1):data(data),l(l),r(r),lay(lay){}
 20 };
 21 int n;
 22 int in[N];
 23 int post[N];
 24 vector<int>le[N];
 25 int cnt;
 26 int max_level=INT_MIN;
 27 node *build_tree(int postl,int postr,int inl,int inr)
 28 {
 29     if(postl>postr)
 30     {
 31         return NULL;
 32     }
 33     node *root=new node;
 34     root->data=post[postr];
 35     int k;
 36     for(k=inl;k<=inr;k++)
 37     {
 38         if(in[k]==post[postr])
 39         {
 40             break;
 41         }
 42     }
 43     int numleft=k-inl;
 44     root->l=build_tree(postl,postl+numleft-1,inl,k-1);
 45     root->r=build_tree(postl+numleft,postr-1,k+1,inr);
 46     return root;
 47 
 48 }
 49 void bfs(node *&root)
 50 {
 51     queue<node*>q;
 52     q.push(root);
 53     root->lay=1;
 54     while(!q.empty())
 55     {
 56            node *tmp=q.front();
 57         q.pop();
 58         le[tmp->lay].push_back(tmp->data);
 59         if(tmp->lay>max_level)
 60         max_level=tmp->lay;
 61         if(tmp->l!=NULL)
 62         {
 63             tmp->l->lay=tmp->lay+1;
 64             q.push(tmp->l);
 65         }
 66         if(tmp->r!=NULL)
 67         {
 68             tmp->r->lay=tmp->lay+1;
 69             q.push(tmp->r);
 70         }
 71     }
 72 }
 73 signed main()
 74 {
 75     IOS;
 76     cin>>n;
 77     for(int i=0;i<n;i++)
 78     {
 79         cin>>in[i];
 80     }
 81     for(int i=0;i<n;i++)
 82     {
 83         cin>>post[i];
 84     }
 85     node *root=build_tree(0,n-1,0,n-1);
 86     bfs(root);
 87     for(int i=1;i<=max_level;i++)
 88     {
 89         if(i&1)
 90         {
 91             for(int j=le[i].size()-1;j>=0;j--)
 92             {
 93                 cout<<le[i][j];
 94                 cnt++;
 95                 if(cnt<n)
 96                 cout<<" ";
 97             }
 98         }
 99         else
100         {
101             for(int j=0;j<le[i].size();j++)
102             {
103                 cout<<le[i][j];
104                 cnt++;
105                 if(cnt<n)
106                 cout<<" ";
107             }
108         }
109     }
110     return 0;
111 }
112                                                                                   

 1 //还是一道思路想通了就好做的题目
 2 //这道题还是运用了BST中序序列是有序的性质
 3 //我们在输入数组对数组进行排序后可用中序遍历对这棵树进行还原
 4 //然后其余的交给bfs就可以了
 5 //这道题因为涉及到-1表示没子节点，所以说用静态二叉树比较好写
 6 #include<bits/stdc++.h>
 7 using namespace std;
 8 #define int long long 
 9 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
10 const int N=110;
11 int n;
12 int cnt;
13 struct node
14 {
15     int data;
16     int l;
17     int r;
18 }t[N];
19 int a[N];
20 int num;
21 void bfs(int root)
22 {
23     queue<int>q;
24     q.push(root);
25     while(!q.empty())
26     {
27         int tmp=q.front();
28         q.pop();
29         cout<<t[tmp].data;
30         num++;
31         if(num<n)
32         {
33             cout<<" ";
34         }
35         if(t[tmp].l!=-1)
36             q.push(t[tmp].l);
37         if(t[tmp].r!=-1)
38             q.push(t[tmp].r);
39     }
40 }
41 void inorder(int root)
42 {
43     if(root!=-1)
44     {
45         inorder(t[root].l);
46         t[root].data=a[cnt++];
47         inorder(t[root].r);
48     }
49 }
50 signed main()
51 {
52     IOS;
53     int lc,rc;
54     cin>>n;
55     for(int i=0;i<n;i++)
56     {
57         cin>>lc>>rc;
58         t[i].l=lc;
59         t[i].r=rc;
60     }
61     for(int i=0;i<n;i++)
62         cin>>a[i];
63     sort(a,a+n);
64     inorder(0);
65     bfs(0);
66     
67     return 0;
68 }

 1 //题意是给定一个序列，要求输出一个完全二叉搜索树的层序序列
 2 //这道题考察的是BST的一个性质--中序序列是有序的
 3 //所以说这道题对给定序列进行排序之后，用中序遍历为其还原就可以得到他原来的层序序列
 4 //代码量不多，但需要想清楚思路
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 #define int long long 
 8 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 9 const int N=1e3+10;
10 struct node
11 {
12     int data;
13     int l;
14     int r;
15     node(int data=0,int l=-1,int r=-1):data(data),l(l),r(r){}
16 }t[N];
17 int n;
18 int a[N];
19 int le[N];
20 int cnt=1;
21 void inorder(int root)
22 {
23     if(root<=n)
24     {
25         inorder(root*2);
26         le[root]=a[cnt++];
27         inorder(root*2+1);
28     }
29 }
30 signed main()
31 {
32     IOS;
33     cin>>n;
34     for(int i=1;i<=n;i++)
35     {
36         cin>>a[i];
37     }
38     sort(a+1,a+1+n);
39     inorder(1);
40     for(int i=1;i<=n;i++)
41     {
42         cout<<le[i];
43         if(i<n)
44         cout<<" ";
45     }
46     return 0;
47 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e2+10;
 4 struct node
 5 {
 6     int data;
 7     vector<int>child;
 8 }t[N];
 9 int n,m,s;
10 int path[N];
11 bool cmp(int a,int b)
12 {
13     return t[a].data>t[b].data;
14 }
15 void dfs(int index,int num,int sum)
16 {
17       if(sum>s)
18       {
19           return ;
20       }
21     if(sum==s)
22     {
23         if(t[index].child.size()==0)
24         {
25             for(int i=0;i<num;i++)
26             {
27                 cout<<t[path[i]].data;
28                 if(i<num-1)
29                     cout<<" ";
30             }
31             cout<<endl;
32         }
33         else
34             return ;
35     }
36     for(int i=0;i<t[index].child.size();i++)
37     {
38         int child=t[index].child[i];
39         path[num]=child;
40         dfs(child,num+1,sum+t[child].data);
41     }
42 }
43 int main()
44 {
45    // IOS;
46     cin>>n>>m>>s;
47     for(int i=0;i<n;i++)
48     {
49         cin>>t[i].data;
50     }
51     for(int i=0;i<m;i++)
52     {
53         int id,k,tmp;
54         cin>>id>>k;
55         for(int j=0;j<k;j++)
56         {
57             cin>>tmp;
58             t[id].child.push_back(tmp);
59         }
60         sort(t[id].child.begin(),t[id].child.end(),cmp);
61     }
62     dfs(0,1,t[0].data);
63     return 0;
64 }

 1 //典型的通过搜索来找最深的层数来计算某个值的问题
 2 //其中的几个点
 3 //递归边界是是否到了叶节点
 4 //引文本题还需要统计相同深度的叶节点的个数
 5 //所以说引入了一个num来记录同层次叶节点的个数
 6 //因为这个题没有涉及到值的问题所以就只用了数组来记录
 7 //这个题其实应该与1079区别开，1079是1090的升级版
 8 #include<bits/stdc++.h>
 9 using namespace std;
10 #define int long long 
11 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
12 const int N=1e5+10;
13 int n;
14 double p,r;
15 vector<int>child[N];
16 double ans;
17 int maxdepth,num;
18 int root;
19 void dfs(int index,int depth)
20 {
21     if(child[index].size()==0)
22     {
23         if(depth>maxdepth)
24         {
25             maxdepth=depth;
26             num=1;
27         }
28         else if(depth==maxdepth)
29         {
30             num++;
31         }
32         return ;
33     }
34     for(int i=0;i<child[index].size();i++)
35     {
36         dfs(child[index][i],depth+1);
37     }
38 }
39 
40 signed main()
41 {
42     IOS;
43     cin>>n>>p>>r;
44     r=r/100;
45     int k;
46     for(int i=0;i<n;i++)
47     {
48         cin>>k;
49         if(k!=-1)
50         {
51             child[k].push_back(i);
52         }
53         else{
54             root=i;
55         }
56     }
57     dfs(root,0);
58     ans=p*pow((1+r),maxdepth);
59     printf("%.2f %lld",ans,num);
60     return 0;
61 }

 1 //同1090说的，是1090的升级版，在此基础上加了叶节点存在货物的数量
 2 //需要的注意的几个点
 3 //如果k是0就说明这个点是叶节点，那就输入他的货物个数就可以了
 4 //如果不是，就代表他的孩子的个数，然后输入他孩子的id
 5 //其余就是dfs了
 6 #include<bits/stdc++.h>
 7 using namespace std;
 8 #define int long long 
 9 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
10 const int N=1e5+10;
11 struct node
12 {
13     int data;
14     vector<int>child;
15 }t[N];
16 int n;
17 double p,r;
18 double ans;
19 void dfs(int index,int depth)
20 {
21     if(t[index].child.size()==0)
22     {
23           ans+=t[index].data*pow((1+r),depth);
24         return ;
25     }
26     for(int i=0;i<t[index].child.size();i++)
27     {
28         dfs(t[index].child[i],depth+1);
29     }
30 
31 }
32 signed main()
33 {
34     IOS;
35     cin>>n>>p>>r;
36     int k,tmp;
37     r=r/100;
38     for(int i=0;i<n;i++)
39     {
40         cin>>k;
41         if(k==0)
42         {
43             cin>>t[i].data;
44         }
45         else{
46             for(int j=0;j<k;j++)
47             {
48                 cin>>tmp;
49                 t[i].child.push_back(tmp);
50             }
51         }
52     }
53     dfs(0,0);
54     ans=ans*p;
55     printf("%.1f",ans);
56     return 0;
57 }

 1 //同1090说的，是1090的升级版，在此基础上加了叶节点存在货物的数量
 2 //需要的注意的几个点
 3 //如果k是0就说明这个点是叶节点，那就输入他的货物个数就可以了
 4 //如果不是，就代表他的孩子的个数，然后输入他孩子的id
 5 //其余就是dfs了
 6 #include<bits/stdc++.h>
 7 using namespace std;
 8 #define int long long 
 9 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
10 const int N=1e5+10;
11 struct node
12 {
13     int data;
14     vector<int>child;
15 }t[N];
16 int n;
17 double p,r;
18 double ans;
19 void dfs(int index,int depth)
20 {
21     if(t[index].child.size()==0)
22     {
23           ans+=t[index].data*pow((1+r),depth);
24         return ;
25     }
26     for(int i=0;i<t[index].child.size();i++)
27     {
28         dfs(t[index].child[i],depth+1);
29     }
30 
31 }
32 signed main()
33 {
34     IOS;
35     cin>>n>>p>>r;
36     int k,tmp;
37     r=r/100;
38     for(int i=0;i<n;i++)
39     {
40         cin>>k;
41         if(k==0)
42         {
43             cin>>t[i].data;
44         }
45         else{
46             for(int j=0;j<k;j++)
47             {
48                 cin>>tmp;
49                 t[i].child.push_back(tmp);
50             }
51         }
52     }
53     dfs(0,0);
54     ans=ans*p;
55     printf("%.1f",ans);
56     return 0;
57 }

  1 //这道题是要求一棵树的有最多子节点的个数和该节点所在的层数
  2 //有bfs和dfs两种解法
  3 //bfs 的思路是定义一个max_depth数组来记录该层的子代个数
  4 //然后就是常规的bfs思路
  5 //需要注意的点是无论是bfs还是dfs这道题的cnt，num都必须设为1，因为开始的时候他是有一个节点的，别问我为什么知道
  6 /*#include<bits/stdc++.h>//bfs
  7 using namespace std;
  8 #define int long long 
  9 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 10 const int N=1e2+10;
 11 struct node
 12 {
 13     int lay;
 14     vector<int>child;
 15 }t[N];
 16 int n,m;
 17 int num=1;
 18 int cnt=1;
 19 int max_depth[N];
 20 void bfs(int root)
 21 {
 22    //max_depth[root]=1;
 23     t[root].lay=1;
 24     queue<int>q;
 25     q.push(root);
 26     while(!q.empty())
 27     {
 28         int tmp=q.front();
 29         q.pop();
 30         max_depth[t[tmp].lay]++;
 31         for(int i=0;i<t[tmp].child.size();i++)
 32         {
 33             int c=t[tmp].child[i];
 34             t[c].lay=t[tmp].lay+1;
 35             q.push(c);
 36         }
 37     }
 38 }
 39 signed main()
 40 {
 41     IOS;
 42     cin>>n>>m;
 43     int k,id,tmp;
 44     for(int i=0;i<m;i++)
 45     {
 46         cin>>id>>k;
 47         for(int j=0;j<k;j++)
 48         {
 49             cin>>tmp;
 50             t[id].child.push_back(tmp);
 51         }
 52     }
 53     bfs(1);
 54     for(int i=2;i<n;i++)
 55     {
 56         if(max_depth[i]>cnt)
 57         {
 58             cnt=max_depth[i];
 59             num=i;
 60         }
 61     }
 62     cout<<cnt<<" "<<num;
 63     return 0;
 64 }*/
 65 //dfs的思路除去相同与bfs的思路以外
 66 //还有就是进入dfs 的函数入口时要对每一层的节点的个数进行加一，对该层的节点数进行统计
 67 #include<bits/stdc++.h>//dfs
 68 using namespace std;
 69 #define int long long 
 70 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 71 const int N=1e2+10;
 72 vector<int>child[N];
 73 int n,m;
 74 int num=1;
 75 int cnt=1;
 76 int max_depth[N];
 77 void dfs(int index,int level)
 78 {
 79     max_depth[level]++;//对该层的节点数进行统计
 80     for(int i=0;i<child[index].size();i++)
 81     {
 82         dfs(child[index][i],level+1);
 83     }
 84 }
 85 signed main()
 86 {
 87     IOS;
 88     cin>>n>>m;
 89     int k,id,tmp;
 90     for(int i=0;i<m;i++)
 91     {
 92         cin>>id>>k;
 93         for(int j=0;j<k;j++)
 94         {
 95             cin>>tmp;
 96             child[id].push_back(tmp);
 97         }
 98     }
 99        dfs(1,1);
100     for(int i=2;i<n;i++)
101     {
102         if(max_depth[i]>cnt)
103         {
104             cnt=max_depth[i];
105             num=i;
106         }
107     }
108     cout<<cnt<<" "<<num;
109     return 0;
110 }

  1 //题意很简单，统计每层叶节点的个数
  2 //还是老样子，bfs和dfs方法都有
  3 //dfs:定义一个max_depth来来表示最深的层数，每次进入入口都统计最深的层数
  4 //如果碰到了叶节点那当前层数的叶子的个数就加一
  5 //然后在遍历其他节点
  6 //老生长谈的一点是输出格式
  7 /*#include<bits/stdc++.h>//dfs
  8 using namespace std;
  9 #define int long long 
 10 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 11 const int N=1e2+10;
 12 int n,m;
 13 int leaf[N];
 14 int max_depth=1;
 15 vector<int>g[N];
 16 void dfs(int index,int depth)
 17 {
 18     max_depth=max(depth,max_depth);
 19     if(g[index].size()==0)
 20     {
 21         leaf[depth]++;
 22     }
 23     for(int i=0;i<g[index].size();i++)
 24     {
 25         dfs(g[index][i],depth+1);
 26     }
 27 }
 28 signed main()
 29 {
 30     IOS;
 31     cin>>n>>m;
 32     int id,k,tmp;
 33     for(int i=0;i<m;i++)
 34     {
 35         cin>>id>>k;
 36         for(int j=0;j<k;j++)
 37         {
 38             cin>>tmp;
 39             g[id].push_back(tmp);
 40         }
 41     }
 42     dfs(1,1);
 43     for(int i=1;i<=max_depth;i++)
 44     {
 45         cout<<leaf[i];
 46         if(i<max_depth)
 47         cout<<" ";
 48     }
 49     return 0;
 50 }*/
 51 //bfs：除了不同于上述dfs的做法之外，擦其实思路也是一样的
 52 //这里对数组加了一个附加属性lay来表示当前层数，其实就是上面的dfs的第二个参数depth
 53 //这里没什么可强调的
 54 #include<bits/stdc++.h>
 55 using namespace std;
 56 #define int long long 
 57 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 58 const int N=1e2+10;
 59 int n,m;
 60 struct node
 61 {
 62     int lay;
 63     vector<int>child;
 64 }t[N];
 65 int max_depth=1;
 66 int leaf[N];
 67 void bfs(int root)
 68 {
 69     t[root].lay=1;
 70     queue<int>q;
 71     q.push(root);
 72     while(!q.empty())
 73     {
 74         int newn=q.front();
 75         q.pop();
 76         max_depth=max(t[newn].lay,max_depth);
 77         if(t[newn].child.size()==0)
 78         {
 79             leaf[t[newn].lay]++;
 80         }
 81         for(int i=0;i<t[newn].child.size();i++)
 82         {
 83             int c=t[newn].child[i];
 84             t[c].lay=t[newn].lay+1;
 85             q.push(c);
 86         }
 87     }
 88 }
 89 signed main()
 90 {
 91     IOS;
 92     cin>>n>>m;
 93     int k,id,tmp;
 94     for(int i=0;i<m;i++)
 95     {
 96         cin>>id>>k;
 97         for(int j=0;j<k;j++)
 98         {
 99             cin>>tmp;
100             t[id].child.push_back(tmp);
101         }
102     }
103     bfs(1);
104     for(int i=1;i<=max_depth;i++)
105     {
106         cout<<leaf[i];
107         if(i<max_depth)
108         cout<<" ";
109     }
110     return 0;
111 }