题面描述:

塔子哥精通二分查找，但对二叉搜索树不太了解。他手中有一棵平衡的满二叉搜索树，节点的左子树包含小于当前节点的数，右子树包含大于当前节点的数，且每个子树也符合二叉搜索树的特性。现在，塔子哥给你一个待查找的整数，请你输出查找路径及结果。输入包括两部分：第一行是 $2^n - 1$ 个整数，表示满二叉搜索树的节点值；第二行是待查找的整数。输出一个字符串，表示从根节点开始的查找路径，其中 S 表示起点，R 表示查找右子树，L 表示查找左子树，找到目标数后用 Y 表示，若未找到则用 N 表示。

思路

从根节点开始查找，标记S，待查找数8比4大,所以查找右树，标记R，8比6还大，继续查找右树标记R，8比右树节点7还大，但已经到了叶子，没有找到，因此最终标记SRRN。

模拟

题目说明给出的是一棵平衡的满二叉树，且节点个数是$2^n-1$，所以构造该二叉树的方法其实和给定的顺序无关。

假设节点个数$m=2^n-1$，编号为$1,2,...,m$。那么根节点编号就是$\lfloor{\frac{1+m}{2}}\rfloor$。之后，左子树的编号范围就变成了$[1,\lfloor{\frac{1+m}{2}}\rfloor-1]$，而右子树的范围就变成了$[\lfloor{\frac{1+m}{2}}\rfloor+1,m]$。如此往复。所以我们只需要将目标值与当前节点编号比较，并判断是走左子树还是右子树就行了。

为了模拟这一过程，我们设定子树编号范围为$L$和$R$。并在上述过程中更新$L$和$R$的值即可。

比如当前节点编号为$p$，要走左子树，那么$R=p-1$，走右子树，$L=p+1$

题解

塔子哥精通二分查找，但对二叉搜索树却不太了解。现有一棵平衡的满二叉搜索树，节点的左子树只包含小于当前节点的值，右子树只包含大于当前节点的值，并且每个子树本身也是二叉搜索树。塔子哥给你一个待查找的整数，请你输出查找路径及结果。

输入分为两部分：第一行包含 $2^n - 1$ 个整数，表示整棵满二叉搜索树的节点值；第二行包含一个待查找的整数。输出一个字符串，表示从根节点开始的查找路径。路径中的符号定义如下：

• S 表示起点（根节点）。
• L 表示查找左子树。
• R 表示查找右子树。
• Y 表示找到目标数。
• N 表示未找到目标数。

代码逻辑分析

1. 输入处理：通过循环读取输入的节点值，直到没有输入为止，将每个值存储在数组 a 中。
2. 目标数设定：在读取完成后，最后一个输入值被设定为待查找的目标数。
3. 查找路径构建：
   • 初始化路径字符串为 S，表示从根节点开始。
   • 使用变量 l 和 r 分别表示当前查找区间的左边界和右边界，初始时为整棵树的边界。
   • 使用 p 来表示当前查找的节点值，初始时为根节点。
   • 在每次比较中，如果目标数小于当前节点值，更新右边界并查找左子树，路径添加 L；如果目标数大于当前节点值，更新左边界并查找右子树，路径添加 R。
4. 查找结果：当找到目标数后，路径字符串添加 Y，表示找到目标数并输出。

代码

Python

import sys

def main():
    # 读取输入
    input_lines = sys.stdin.read().strip().split("\n")
    if not input_lines:
        return
    
    # 解析输入数据
    a = list(map(int, input_lines[0].split()))  # 读取节点值
    target = int(input_lines[1])  # 目标查找值

    # 先排序，确保满足满二叉搜索树的构造方式
    a.sort()

    # 初始化二分查找
    l, r = 0, len(a) - 1
    path = "S"  # 记录查找路径

    while l <= r:
        mid = (l + r) // 2  # 计算当前子树的根节点
        mid_val = a[mid]  # 当前节点值

        if mid_val == target:
            path += "Y"
            print(path)
            return
        elif target < mid_val:
            path += "L"
            r = mid - 1  # 进入左子树
        else:
            path += "R"
            l = mid + 1  # 进入右子树
    if len(path)>0:
        path = path[0:-1]
    # 目标未找到
    path += "N"
    print(path)

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取输入
        String[] inputArr = sc.nextLine().split(" ");
        int[] a = Arrays.stream(inputArr).mapToInt(Integer::parseInt).toArray();
        int target = sc.nextInt();
        
        // 先排序，确保满足满二叉搜索树的构造方式
        Arrays.sort(a);

        // 二分查找
        int l = 0, r = a.length - 1;
        StringBuilder path = new StringBuilder("S"); // 记录查找路径

        while (l <= r) {
            int mid = (l + r) / 2;
            int midVal = a[mid];

            if (midVal == target) {
                path.append("Y");
                System.out.println(path);
                sc.close();
                return;
            } else if (target < midVal) {
                path.append("L");
                r = mid - 1;
            } else {
                path.append("R");
                l = mid + 1;
            }
        }
        
        if (path.length() > 0) {
            path.setLength(path.length() - 1); // 移除最后一个字符
        }
        path.append("N");
        System.out.println(path);
        sc.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>

using namespace std;

int main() {
    string line;
    getline(cin, line); // 读取第一行（节点值）
    
    stringstream ss(line);
    vector<int> a;
    int num;
    while (ss >> num) {
        a.push_back(num);
    }

    int target;
    cin >> target; // 读取目标值

    // 先排序，确保满足满二叉搜索树的构造方式
    sort(a.begin(), a.end());

    // 二分查找
    int l = 0, r = a.size() - 1;
    string path = "S"; // 记录查找路径

    while (l <= r) {
        int mid = (l + r) / 2;
        int midVal = a[mid];

        if (midVal == target) {
            path += "Y";
            cout << path << endl;
            return 0;
        } else if (target < midVal) {
            path += "L";
            r = mid - 1;
        } else {
            path += "R";
            l = mid + 1;
        }
    }

    if (!path.empty()) {
        path.pop_back(); // 移除最后一个字符
    }
    path += "N";
    cout << path << endl;
    return 0;
}

javascript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

(async function () {
    let a = (await readline()).split(" ").map(Number); // 读取节点值
    let target = parseInt(await readline()); // 读取目标值

    // 先排序，确保满足满二叉搜索树的构造方式
    a.sort((x, y) => x - y);

    let l = 0, r = a.length - 1;
    let path = "S"; // 记录查找路径

    while (l <= r) {
        let mid = Math.floor((l + r) / 2);
        let midVal = a[mid];

        if (midVal === target) {
            path += "Y";
            console.log(path);
            rl.close();
            return;
        } else if (target < midVal) {
            path += "L";
            r = mid - 1;
        } else {
            path += "R";
            l = mid + 1;
        }
    }

    if (path.length > 0) {
        path = path.slice(0, -1); // 移除最后一个字符
    }
    path += "N";
    console.log(path);
    rl.close();
})();

题目描述

$\qquad$小明精通二分查找，但是对二叉搜索树却一窍不通，现在小明手里有一棵平衡的满二叉搜索树。由于小明对二叉搜索树这个概念不是很懂，他做了一些笔记如下：

$\qquad$（1）节点的左子树只包含小于当前节点的数。

$\qquad$（2）节点的右子树只包含大于当前节点的数。

$\qquad$（3）所有左子树和右子树自身必须也是二叉搜索树。

$\qquad$为了更好的了解这个数据结构的功能，现在小明给你一个待查整数，请你告诉小明：查找路径以及查询结果。

输入描述

$\qquad$第一行输入$2^n-1$个整数，表示整棵满二叉搜索树。其中$1 \le n \le 10$，整数之间用空格分割。

$\qquad$第二行为一个待查找的整数。

$\qquad$规定：所有整数$num∈[-32768, 32767]$。

输出描述

$\qquad$一个字符串，表示输出搜索路径以及结果

$\qquad$规定：搜索路径起点为根节点，用$S$表示，查找右子树用$R$表示，查找左子树用$L$表示，找到对应整数后用$Y$表示，若最终未找到则用$N$表示。

样例一

输入

2 1 3 7 5 6 4
6

输出

SRY

解释

从根节点开始，所以路径的第一部分为S，待查找数为加6，大于4，所以要查找右树，路径增加R，正好找到，所以最后增加Y，最终输出SRY

样例二

输入

4 2 1 3 6 5 7
5

输出

SRLY

解释

从根节点开始，一次往右树，一次往左树查找，找到结果5，因此最终SRLY

样例三

输入

1 2 3 4 5 6 7
8

输出

SRRN

解释

从根节点开始查找，标记S，待查找数8比4大,所以查找右树，标记R，8比6还大，继续查找右树标记R，8比右树节点7还大，但已经到了叶子，没有找到，因此最终标记SRRN。