[已解决]二叉树访问

柿子饼同学

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

#include <bits/stdc++.h>
using namespace std;

int tree[1005];
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[i];
    }
    cin >> q;
    while(q--){
        cin >> x;
        int l = 1, r = n;
        for(int i = 1; i <= n; i++){
            if(tree[i] >= l && tree[i] <= r){
                if(tree[i] == x){
                    cout << endl;
                    break;
                }
                else if(tree[i] > x){
                    cout << 'E';
                    r = tree[i] - 1;  // 就是这里
                }
                else{
                    cout << 'W';
                    l = tree[i] + 1; // 就是这里
                }
            }
        }
    }
    
    return 0;
}

输入输出 :

4
2 1 4 3
3
1 2 3

E

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