标签：pac 统一 -- mmm gdb调试 png close splay stream
补题：
给定n最大10^5 ，1
样例
6 1
3 1 2 5 4 6
输出
3 5 4 1 6 2
移动后
3
5 1
4 6 2
前序(根左右)3 5 4 1 6 2
前方的k应该是往左移动
[ ---- 代码中的move_val差不多是一横行里面的id、ans是横着记录的值 -----]
1 #include
2 #include 3 #include 4 using namespace std;
5 typedef long long ll;
6 int n, k;
7 int a;
8 int max_depth;
9 bool print_first = true;
10 //vector> ans;
11 vectorint>> ans;
12 struct node{
13 node *left=NULL;
14 node *right=NULL;
15 int val=-1;
16 int move_val = -1;
17 int step = -1;
18 node(int a,int stepp) {
19 val = a;
20 step = stepp;
21 };
22 };
23 void find_and_place(int val,node* p,int step){
24 step = step + 1;
25 if(valval){
26 if(p->left==NULL){
27 node *p2 = new node(val,step);
28 p->left = p2;
29 max_depth = max(max_depth, step);
30 }else{
31 find_and_place(val, p->left,step);
32 }
33 }else{
34 if(p->right==NULL){
35 node *p2 = new node(val,step);
36 p->right = p2;
37 max_depth = max(max_depth, step);
38 }else{
39 find_and_place(val, p->right,step);
40 }
41 }
42 }
43
44 void record(node* p){
45 ans[p->step].push_back(p->val);
46 p->move_val = ans[p->step].size()-1;
47 if(p->left!=nullptr){
48 record(p->left);
49 }
50 if(p->right!=nullptr){
51 record(p->right);
52 }
53 }
54
55
56 void print(node* p){
57 int size = ans[p->step].size();
58 int new_id = (p->move_val + size + k) % size;
59 if(print_first==true){
60 print_first = false;
61 }else{
62 cout " ";
63 }
64 cout step][new_id];//根
65
66
67 if(p->left){
68 print(p->left);
69 }
70 if(p->right){
71 print(p->right);
72 }
73 }
74 int main(){
75 // ans[0].push_back(1);
76 cin >> n >> k;
77 cin >> a;
78 node *root = new node(a,0);
79 //place
80 for (int i = 2; i ){
81 cin >> a;
82 find_and_place(a,root,0);
83 }
84 //vector > ans push
85 vectorint> v;
86 for (int i = 0; i ){
87 ans.push_back(v);
88 }
89 //move
90 record(root);
91
92 //print
93 print(root);
94 cout endl;
95
96 system("pause");
97 return 0;
98 }
View Code
指针如果不初始化成NULL 怕是有随机变量、因为它并不是全局变量哦，但是NULL的话再初始化就是规范的0x0(十六进制地址)
这里一直往下left似乎没问题，在gdb调试下，就是这样的[并不是多重循环不停导致..,.,.]
标准的写法 建的树还挺完整的？先看，如果小了就往左，子已经NULL了就挂那，不null就继续找left那边
depth不对了，建树的时候，树、子树没搞明白；子树生成的时候depth应该+1，max_depth也要记录+1，root的应该是1，就生成的时候也统一一下是1
emmm... 但是，vector套vector可不这么想，它 是从0开始计数的，那么这儿就错了=_=
修改了从0开始计数后，ans还少了一块，我一看我ans是从1开始push到n，但实际上vector里可并不是这样【和数组不同，数组可以赋值1-n，vector天然从0开始的呐】
那么以上都是vector的问题，解决了这个~~ record没问题了，开始print
这里是vector[ans] 不仅记录了当前的序号，（子树的横向顺序信号），还记录了子树的值
move_val实际上是: id
在子树的值，这一横排里，比如
2 4 6 8
实际上我是往前移动了k才得到的，那么我的序号就是(p->move_val + size+k)%size
我们可以知道这个move_val实际上是id，就是它是这一横排里面的第几个。
不能简单的+2，我们可以看到是往前移，那么是+k就好了，当时-2应该是特定的3个情况下……
为了避免越界，+size再%size
为了解决下标问题，直接从0开始吧，给move_val(也就是id)也从0开始记录
现在调整一下输出，既然正常前序没问题，那么---？
先看ans，好吧，发现ans是错的，那么应该各个depth都有错
啊这，竟然还是前面忘记step+1的小bug，看来应该每次进入直接+1~
现在看就没什么大问题了，主要是小问题不断，大思路没什么问题，总结如下：
（1）step的0/1关系搞错（子树应该+1、有个地方漏了+1）
（2）vector套vector那个ans没有push好，0和1搞错，不统一
(3)k是往前，样例没完全搞懂，只看片面3个导致错
试试其他样例呢？k=2没啥问题。
7 5
5 9 8 14 12 4 3
也没啥问题。那就这样吧
笔试题: 二叉排序数左移k个
标签：pac 统一 -- mmm gdb调试 png close splay stream
原文地址：https://www.cnblogs.com/lx2331/p/14771256.html