[已解决]二叉树访问

柿子饼同学

题目 , 代码贴上 , 有点不理解代码
思路是不是 : 先给它一个范围 , 由于二叉搜索树的性质 (左边比根小,  右边比根大) 然后可以确定走的方向
但是为什么范围的确定与 tree[i] 有关 ? 万一当前访问的是别的子树呢 ?

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int tree[1005];
   
5. int n, q, x;
   
6. 
   
7. 
   
8. int main(){
   
9.     ios::sync_with_stdio(0);
   
10.     cin.tie(0); cout.tie(0);
    
11.    
    
12.     cin >> n;
    
13.     for(int i = 1; i <= n; i++){
    
14.         cin >> tree[i];
    
15.     }
    
16.     cin >> q;
    
17.     while(q--){
    
18.         cin >> x;
    
19.         int l = 1, r = n;
    
20.         for(int i = 1; i <= n; i++){
    
21.             if(tree[i] >= l && tree[i] <= r){
    
22.                 if(tree[i] == x){
    
23.                     cout << endl;
    
24.                     break;
    
25.                 }
    
26.                 else if(tree[i] > x){
    
27.                     cout << 'E';
    
28.                     r = tree[i] - 1;  // 就是这里
    
29.                 }
    
30.                 else{
    
31.                     cout << 'W';
    
32.                     l = tree[i] + 1; // 就是这里
    
33.                 }
    
34.             }
    
35.         }
    
36.     }
    
37.    
    
38.     return 0;
    
39. }
    

复制代码

输入输出 :

1. 4
   
2. 2 1 4 3
   
3. 3
   
4. 1 2 3

复制代码

1. E
   
2. 
   
3. WE

复制代码

最佳答案

月排行榜 / 总排行榜

dolly_yos2

2022-7-16 18:53:29

这里的 l 和 r 框定了当前处理的子树中节点值的范围。由于输入是 1 到 n 的一个排列，因此节点在当前考察的子树当且仅当其值在 l 和 r 确定的范围之内。从代码也能看出，遍历中不在范围的点不会被处理。另外由于按照输入的顺序向空树插入值，输入序列中最先出现的属于当前子树的节点一定是该子树的根，因此根据其值确定已经找到还是选定新的子树，即调整 l 和 r 的值。

跳转到最佳答案楼层

柿子饼同学

救救我

dolly_yos2

这里的 l 和 r 框定了当前处理的子树中节点值的范围。由于输入是 1 到 n 的一个排列，因此节点在当前考察的子树当且仅当其值在 l 和 r 确定的范围之内。从代码也能看出，遍历中不在范围的点不会被处理。另外由于按照输入的顺序向空树插入值，输入序列中最先出现的属于当前子树的节点一定是该子树的根，因此根据其值确定已经找到还是选定新的子树，即调整 l 和 r 的值。

柿子饼同学

dolly_yos2 发表于 2022-7-16 18:53
这里的 l 和 r 框定了当前处理的子树中节点值的范围。由于输入是 1 到 n 的一个排列，因此节点在当前考察的 ...

懂了 ， 谢谢

hornwong