题目大意：给定一个二叉树，求让它成为孩子结点值不大于父亲结点值，同时左孩子结点值小于右孩子结点值。
用广搜建立二叉树，再后序遍历，求最长不下降子序列，我做了一点变化，将左右孩子交换后先序遍历后求最长不上升子序列。
开始超时了，后来把队列用数组实现就行了，不过注意一下没有右孩子时，左孩子可以和父亲结点值相等。
1
//poj 3214
2#include<iostream>
3#include<queue>
4using namespace std;
5#define N 10000000
6
7struct Tree
{
8
int v;
9 Tree *left;
10 Tree *right;
11
void init(){
12 left=0;
13 right=0;
14
}
15
};
16
17Tree set[N],*p;
18int n,m,cot,len=1;
19int b[N];
20Tree *myque[N];
21
22void dfs(Tree *q)
23{
24 int x;
25 x=q->v+cot,m++;
26 //LIS
27 int low=1,high=len,mid;
28 while(low<=high){
29 mid=(low+high)/2;
30 if(b[mid]<x) high=mid-1;
31 else low=mid+1;
32 }
33 b[low]=x;
34 if(low>len) len++;
35
36 if(q->right)
37 dfs(q->right);
38 if(q->left){
39 if(q->right) cot++; //存在左孩子时才将cot++
40 dfs(q->left);
41 }
42}
43
44int main()
45{
46 int v;
47 int low=0,high=0;
48 n=0;
49 scanf("%d",&m);
50 set[0].init();
51 scanf("%d",&set[0].v);
52 myque[high++]=&set[0];
53 while(scanf("%d",&v)!=EOF){
54 p=myque[low++];
55 set[++n].init();
56 set[n].v=v;
57 p->left=&set[n];
58 myque[high++]=p->left;
59 if(scanf("%d",&v)!=EOF){ //注意可能不是满二叉树
60 set[++n].init();
61 set[n].v=v;
62 p->right=&set[n];
63 myque[high++]=p->right;
64 }
65 else break;
66 }
67 m=0,cot=0;
68 dfs(&set[0]);
69 printf("%d\n",m-len);
70 return 0;
71}
72