题目描述

$\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。

题面描述:

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

思路

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

模拟