题目描述

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

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

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

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

题面描述:

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

思路

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

模拟