题解 P3365 【改造二叉树】

题目求的是一颗二叉树改为二叉搜索树的最少步骤 因为二叉搜索树的中序遍历一定是一个由小到大的最长上升子序列 所以我们只需要中序遍历这颗二叉树 将他的中序遍历出的结点依次放入一个数组 然后求一遍最长上升子序列的长度，用总个数减去这个满足要求的长度，就得到了要修改的点数 但是由于题目中整数的限制，所以求最长不降而不是上升 提一点，最长不下降用lower——bound 最长上升用upper——bound 减的是d的长度哦 最后如果有童鞋不会求lis（最长上升子序列），给你看一个大神博客哦，他讲的很清楚。你可以先看了，才知道为什么后面的那个for循环要这样写的哦！ [求最长上升、不降子序列](https://www.cnblogs.com/itlqs/p/5743114.html) 美美哒代码送给你，请接收！ ```cpp #include <iostream> #include <cstdio> const int maxn=500100; using namespace std; struct NODE{ int key,lc,rc; }node[maxn]; int shuzu[maxn],d[maxn]; int n,a,b,k; void midsearch(int u){ if(node[u].lc)midsearch(node[u].lc); //这一步是为什么？ //因为当i到j是递增，他们值也是递增的情况时，因为i到j的值差一定要大于等于i到j的下标差，不然怎么递增啊？即aj-ai>=j-i,即aj-j>=ai-i， //这样我们再去求lis shuzu[++k]=node[u].key-k;//k是点依次进入数组的编号，中序遍历的顺序 if(node[u].rc)midsearch(node[u].rc); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&node[i].key); } for(int i=2;i<=n;i++){//大家输入搞对了嘛？第一个数是节点，后一个数是说i是他的什么儿子，所以i从2开始好些 scanf("%d%d",&a,&b); if(b){ node[a].rc=i; } else node[a].lc=i; } midsearch(1); d[1]=shuzu[1]; int len=1; for(int i=2;i<=n;i++){ if(shuzu[i]>=d[len]){ d[++len]=shuzu[i]; } else{ int j=lower_bound(d+1,d+1+len,shuzu[i])-d;//减去d的长度你减了吗？ d[j]=shuzu[i]; } } printf("%d",n-len); return 0; } ```