Hdu 5444 Elven Postman dfs

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=5444

题意:

给你n个数字，这n个数字是按照二叉搜索树的节点特性给你的，让你建好这棵二叉搜索树，然后，再给出一些询问，让你回答从根节点到某个节点该怎么走？
http://www.cnblogs.com/zyf0163/p/4805218.html?tvd 样例解释的题意

题解:

dfs： http://www.cnblogs.com/qscqesze/p/4805305.html Orz 居然可以这样写
树的形态是唯一的
我们可以处理每个节点能够放的点的大小的范围，然后就可以求出这棵树的样子了
回答就可以顺便再DFS建树的过程中处理出来

建树：http://www.cnblogs.com/wikioibai/p/4810534.html
按照左子树<根节点<右子树的方式来建树，然后再根据这种方式从根节点开始查询就可以了。

代码:

代码一： dfs

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 int p[maxn];
19 int n,ctt;
20 vector<int> qq;
21 
22 struct node{
23     string str;
24     int L,R;
25 }c[maxn];
26 
27 int dfs(int u){
28     if(ctt == n+1) return true;
29     while(1){
30         if(c[u].L<=p[ctt] && p[ctt]<=c[u].R){
31             int x = p[ctt];
32             int y = u;
33             if(x < y){
34                 c[x].str = c[u].str + "E";
35                 c[x].L = c[u].L;
36                 c[x].R = y;
37             }else{
38                 c[x].str = c[u].str + "W";
39                 c[x].L = y;
40                 c[x].R = c[u].R;
41             }
42             ctt++;
43             if(ctt == n+1) return true;
44             if(dfs(x)) return true;
45         }else
46             return false;
47         if(ctt == n+1) return true;
48     }
49 }
50 
51 int main(){
52     int T=read();
53     while(T--){
54         qq.clear();
55         n = read();
56         for(int i=1; i<=n; i++){
57             p[i] = read();
58         }
59         int q = read();
60         for(int i=1; i<=q; i++){
61             int x = read();
62             qq.push_back(x);
63         }
64         for(int i=1; i<=n; i++){
65             c[i].str = "";
66             c[i].L=-10000,c[i].R=10000;
67         }
68         ctt = 2;
69         dfs(p[1]);
70 
71         for(int i=0; i<(int)qq.size(); i++)
72             cout << c[qq[i]].str << endl;
73     }
74 
75     return 0;
76 }

代码二：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 struct Node{
19     int val;
20     int child[2];
21     Node(int k=0){
22         this->val = k;
23         MS(child);
24     }
25 };
26 
27 struct Tree{
28     Node node[maxn];
29     int sz;
30     void init(){
31         sz = 0;
32     }
33     int newnode(int x){
34         node[++sz] = Node(x);
35         return sz;
36     }
37 
38     void insert(int &u, int x){ // 引用真是妙 
39         if(u == 0){
40             u = newnode(x);
41             return ;
42         }
43         if(node[u].val > x){
44             insert(node[u].child[0],x);
45         }else{
46             insert(node[u].child[1],x);
47         }
48     }
49 
50     void find(int u,int x){
51         if(u == 0){
52             return ;
53         }
54         if(node[u].val > x){
55             printf("E");
56             find(node[u].child[0],x);
57         }else if(node[u].val < x){
58             printf("W");
59             find(node[u].child[1],x);
60         }
61 
62     }
63 }tree;
64 
65 
66 int main(){
67     int T=read();
68     while(T--){
69         int n = read();
70         int root = 0;
71         tree.init();
72         for(int i=1; i<=n; i++){
73             int x = read();
74             tree.insert(root,x);
75         }
76 
77         int q = read();
78         while(q--){
79             // cout << "rr " << root << endl;
80             int x=read();
81             tree.find(root,x);
82             puts("");
83         }
84     }
85 }