二叉树访问
题目 , 代码贴上 , 有点不理解代码思路是不是 : 先给它一个范围 , 由于二叉搜索树的性质 (左边比根小,右边比根大) 然后可以确定走的方向
但是为什么范围的确定与 tree 有关 ? 万一当前访问的是别的子树呢 ?
#include <bits/stdc++.h>
using namespace std;
int tree;
int n, q, x;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> tree;
}
cin >> q;
while(q--){
cin >> x;
int l = 1, r = n;
for(int i = 1; i <= n; i++){
if(tree >= l && tree <= r){
if(tree == x){
cout << endl;
break;
}
else if(tree > x){
cout << 'E';
r = tree - 1;// 就是这里
}
else{
cout << 'W';
l = tree + 1; // 就是这里
}
}
}
}
return 0;
}
输入输出 :
4
2 1 4 3
3
1 2 3
E
WE {:10_266:}{:10_266:}{:10_266:}
救救我 这里的 l 和 r 框定了当前处理的子树中节点值的范围。由于输入是 1 到 n 的一个排列，因此节点在当前考察的子树当且仅当其值在 l 和 r 确定的范围之内。从代码也能看出，遍历中不在范围的点不会被处理。另外由于按照输入的顺序向空树插入值，输入序列中最先出现的属于当前子树的节点一定是该子树的根，因此根据其值确定已经找到还是选定新的子树，即调整 l 和 r 的值。 dolly_yos2 发表于 2022-7-16 18:53
这里的 l 和 r 框定了当前处理的子树中节点值的范围。由于输入是 1 到 n 的一个排列，因此节点在当前考察的 ...
懂了 ， 谢谢 {:5_108:}
页:
[1]