搜索
搜索相关的问题，可以有两类任务，查找和遍历。
- 查找
- 二分搜索
- 顺序查找
- 二叉搜索树
- 无序查找
- 有序查找
- 遍历
- 深度优先遍历（栈的应用）
- 广度优先遍历（队列的应用）
查找
顺序搜索（Sequential Search）
在无序记录集中搜索关键词为key的记录在记录集中的位置i(0 <= i <= n - 1). 它的查找过程是：
- 从第一个开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；
- 如果直到最后一个记录，其关键字和给定值比较都不等时，则没有所查的记录，查找不成功
例子：53 78 65 17 87 9 81 45 23 67
搜索：90 45
从前往后找，如果到末尾都没有找到就没有找到。可以看到，90这个数从头找到尾都没有找到该数，说明查找不成功；45这个数从头找到尾的时候找到了，下标为7，返回所查找的记录。
顺序搜索也叫暴力搜索，其时间复杂度为O(N), N是列表的长度。可以看到这种时间复杂度是比较高的，那么对于无序数组而言，是否能够通过某种方式使得搜索更快一些呢？答案是可以构造二叉搜索树，然后再进行查找，能够将查找时间复杂度变为O(logN)
二叉搜索树(Binary Search Tree, BST)
二叉搜索树又称二叉排序树。它或者是一颗空树，或者是具有以下性质的二叉树：
- 若它的左子树不空，则左子树所有结点的值均小于它的根结构的值
- 若它的右子树不空，则右子树所有结点的值均大于它的根结构的值
- 它的左右子树也分别为二叉搜索树
- 没有键值相等的结点
例子：53 78 65 17 87 9 81 45 23 67
搜索：90 45
首先通过递归的方式定义二叉搜索树：
- 53，根节点设置为53；
- 53后面跟的是78，由于78大于根节点53， 78节点设置为根节点53的右子节点；
- 78后面跟的是65，由于65大于根节点53，则表明65位于53的右子树，又由于65小于78，则65可以设置为78的左子节点；
- 65后面跟的是17，由于17小于根节点53，则表明17位于53的左子树，17可以设置为53的左子节点；
- 17后面跟的是87，由于87大于根节点53，则表明87位于53的右子树中，又由于87大于78，则87可以设置为78的右子节点；
- 87后面跟的是9，由于19小于根节点53，则表明9位于53的左子树中，又由于9小于17，则9可以设置为17的左子节点；
- 9后面跟的是81，由于81大于根节点53，则表明81位于53的右子树中，又由于81大于78，则81位于78的右子树中，又由于81小于87，则81可以设置为87的左子节点；
- 81后面跟的是45，由于45小于根节点53，则表明45位于53的左子树中，又由于45大于17，则45可以设置为17的右子节点；
- 45后面跟的是23，由于23小于根节点53，则表明23位于53的左子树中，又由于23大于17，则23位于17的右子树中，又由于23小于45，则23可以设置为45的左子节点；
- 23后面跟的是67，由于67大于根节点53，则表明67位于53的右子树中，又由于67小于78，则67位于78的左子树中，又由于67大于65，则67可以设置为65的右子节点；
最终构建的二叉搜索树如下图搜索：
可以看到：二叉搜索树的中序遍历就是顺序序列:
9 17 23 45 53 65 67 78 81 87
二分搜索(Binary Search)
在有序记录集中，每次把待查区间中间位置记录的关键词与key比较，若不等则缩小搜索区间并在新的区间内重复上述过程，直到搜索成功或者搜索区间长度为0 （搜索不成功）为止。
例子：12 23 26 37 54 60 68 75 82 96
搜索：96 24
可以看到序列是有一个有序的，从小到大排序。
查找96：
- left是12，right是96，mid是54，可以看到mid的值小于96，表明位于右半段，left =1
- left是60，right是96，mid是75，可以看到mid的值小于96，表明位于右半段，left =1
- left是82，right是96，mid是82，可以看到mid的值小于96，表明位于右半段，left =1
- left是96，right是96，mid是96，可以看到mid的值正好等于96，返回该下标；
查找24:
- left是12，right是96，mid是54，可以看到mid的值大于24，表明位于左半段，right-=1
- left是12，right是37，mid是23，可以看到mid的值小于24，表明位于右半段，left =1
- left是23， right是37，mid是26，可以看到mid的值大于24，表明位于左半段，right-=1
- left是23，right是26，mid是23，可以看到mid的值小于24，表明位于右半段，left =1
- left是26，right是26，mid是26，可以看到mid的值大于24，表明位于左半段，right-=1
- left是26，right是23，由于left>right，这个表明查找完毕，26不在该列表中；
遍历
深度优先搜索
假设（，） 以S为起点（源点）进行搜索。首先标识S为已访问结点，接着寻找与S相邻的结点w,若w是未被访问结点，则以w为起点进行深度优先搜索，若w是已被访问结点，则寻找其它与s相邻的结点，直到与S有路径相通的所有结点都被访问过.
深度优先搜索：是栈的思想，先入后服务
深度遍历：
以为起始，遍历，再去遍历连接的边节点，再去遍历的边节点，再去遍历的边节点， 再去遍历的边节点和，但是这两个边节点已经遍历过来，所以略过，回到边节点，继续遍历边节点， 遍历的边节点，遍历的边节点，已经遍历过，继续遍历，遍历过，继续遍历边节点，遍历的边节点， 由于已经遍历过，继续遍历节点，由于遍历过，回到，由于遍历过，回到， 遍历过，回到，由于遍历过，活到，由于遍历过，回到， 由于遍历过，回到， 由于遍历过，回到， 由于遍历过，回到， 由于遍历过，返回整个遍历的列表
广度优先搜索
假设（，） 以S为起点（源点）进行搜索。
首先标识S为已访问结点，然后访问S的邻接点,的未被访问的邻接点，以此类 推，直到与S有路径相连的所有结点都被访问到。
广度优先搜索：是队列的思想，先来先服务
层序遍历：
准备一个队列和一个哈希表，队列用来存储遍历的节点，哈希表存储该节点是否被遍历过。
- 首先以为起始，遍历， 入队列
queue，发现这一层就这一个节点, []； - 该队列pop出该节点，再遍历的子节点，和， 如果两个节点都没有被遍历过，这两个节点入队列queue, [, ]
- 第二层有两个节点，首先队列pop出， 再遍历的子节点，， ， 由于已经遍历过，只将和入队列 [, , ]。队列再pop出， 再遍历的子节点，， ，由于已经遍历过，只将和入队列queue， [, , , ]
- 第三层有四个节点，首先队列pop出， 再遍历的子节点，， 由于已经遍历过，只将入队列 [, , ，]。队列再pop出， 再遍历的子节点，，由于和已经遍历过，不将和入队列queue， [, , ] 。队列再pop出,再遍历的子节点，，由于和已经遍历过，不将和入队列queue， [, ] 。队列再pop出,再遍历的子节
- 点，，由于和已经遍历过，不将和入队列queue， []
- 第四层有一个节点，首先队列pop出， 再遍历的子节点，， ，, 由于这些节点已经遍历过，不再入对，最终队列为[]，表明遍历完毕，返回整个遍历的列表
排序搜索是非常热门的问题，熟练掌握二分查找法，二叉搜索法，DFS，BFS等算法。
例题
360 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 :
代码语言：javascript复制输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
解题思路：
- 顺序查找：从头找到尾，如果中间找到则返回结构，如果遍历完毕都没有找到，返回-1，时间复杂度为
- 二分查找：由于序列是一个有序序列，可以利用该性质，设置左右两个节点，每次取中间值与之进行比较，如果大于中间值，表明是位于右半部分，如果小于中间值，表明位于左半部分，如果相等，则返回下标，时间复杂度为。
python实现
代码语言：javascript复制class Solution:
def search(self, nums: List[int], target: int) -> int:
length = len(nums)
left = 0
right = length-1
while left <= right:
mid = left (right-left) // 2
if target == nums[mid]:
return mid
if target < nums[mid]: # left part
right = mid - 1
if target > nums[mid]: # right part
left = mid 1
return -1
C 实现
代码语言：javascript复制class Solution {
public:
int search(vector<int>& nums, int target) {
int size = nums.size();
int left = 0;
int right = size - 1;
while(left <= right)
{
int mid = left (right-left)/2;
if(target == nums[mid])
{
return mid;
}
else if(target < nums[mid])
{
right = mid-1;
}
else
{
left = mid 1;
}
}
return -1;
}
};
30 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k 1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 ：
代码语言：javascript复制输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
输入：nums = [1], target = 0
输出：-1
解题思路：
- 顺序遍历：从头开始遍历，如果找到该元素就返回下标，如果没有找到该元素就返回-1，时间复杂度为
- 二分查找法：由于该列表最开始是有序的，然后经过旋转之后变成不是顺序序列，但观察规律可以看到，序列被分为了两段式有序，还是可以应用二分法来进行查找：
fig1
代码语言：javascript复制0 1 2 3 4 5 6 7 8 经过变换后
3 4 5 6 7 8 0 1 2
查找元素是0
left = 0
right = 7
mid = (0 7)/2 = 3
nums[mid] = 6 此时target=0 小于6的，又由于nums[left] < 6，表明mid在左侧有序序列中。
因此此时有两种情况，左半部分或者右半部分。
如果在左半部分，就直接与left值进行比较
如果比left值小，说明在右半部分，左半部分不做考虑 left = mid 1
如果等于left值，则返回left下标
如果大于left值，说明在左半部分，right=mid-1
如果在右半部分，则left = mid 1， 继续二分查找
python实现
代码语言：javascript复制class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
length = len(nums)
left = 0
right = length - 1
while left <= right:
mid = left (right-left) // 2
if target == nums[mid]:
return mid
if nums[mid] >= nums[left]: # left 和 right
if nums[left] <= target <= nums[mid]:
right = mid - 1
else:
left = mid 1
else:
if nums[mid] < target <= nums[right]:
left = mid 1
else:
right = mid - 1
return -1
c 实现
代码语言：javascript复制class Solution {
public:
int search(vector<int>& nums, int target) {
int length = nums.size();
int left = 0;
int right = length - 1;
while(left <= right)
{
int mid = left (right-left) / 2;
if(target == nums[mid])
{
return mid;
}
if(nums[mid] >= nums[left])
{
if(target >= nums[left] && target <= nums[mid])
{
right = mid - 1;
}
else
{
left = mid 1;
}
}
else
{
if(nums[mid] < target && target <= nums[right])
{
left = mid 1;
}
else
{
right = mid - 1;
}
}
}
return -1;
}
};
78 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
代码语言：javascript复制输入：root = []
输出：[]
示例 3：
代码语言：javascript复制输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[2,1]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
解题思路：
- 递归方式：树的方法一般是使用递归的方式进行解决，中序遍历，可以先递归遍历左子树，再是根节点，再递归遍历右子树，最终结果就是中序遍历
- 迭代方式：深度优先遍历，先深度优先中序遍历左子节点，然后加入根节点，之后深度优先中序遍历右子节点。一直往左找，往栈中放元素，直到找不到下去，栈pop一个元素出来，继续找。
递归实现
- python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
if not root.left and not root.right:
return [root.val]
res = [] # 保存结果
def helper(root):
if not root:
return []
helper(root.left) # 先递归遍历左子节点
res.append(root.val) # 保存根节点
helper(root.right) # 递归遍历右子节点
helper(root)
return res
- c 实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void helper(TreeNode* root, vector<int>& res) // 引用
{
if(!root)
{
return;
}
helper(root->left, res);
res.push_back(root->val);
helper(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
helper(root, res);
return res;
}
};
时间复杂度与空间复杂度最差的情况下都为
迭代实现dfs
- python实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack = []
res = []
while stack or root:
while root:
stack.append(root)
root = root.left # 一直往左找
root = stack.pop()
res.append(root.val) # 然后将root设置为右节点
root = root.right # 然后将root设置为右节点
return res
- c 实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while(root != nullptr || !stk.empty())
{
while(root != nullptr)
{
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}
};
85 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
解题思路：
- 递归方式：如果根节点具有左右节点，判断二者元素是否相等，如果相等，递归判断左右节点的情况，同步移动两个指针遍历树，p指针左移，q指针右移，每次检测当前p和q节点的值是否相等，如果相等再判断左右子树是否对称
- 迭代方式：层次遍历，bfs，如果是轴对称树，则该层的列表是也是轴对称
递归实现
- python实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
return self.check(root, root)
def check(self, p, q):
if not p and not q:
return True
if not p or not q:
return False
return p.val == q.val and self.check(p.left, q.right) and self.check(p.right, q.left)
- c 实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool check(TreeNode* p, TreeNode* q)
{
if(p == nullptr && q == nullptr)
{
return true;
}
if(p==nullptr || q == nullptr)
{
return false;
}
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
迭代bfs实现
首先引入一个队列，初始化时把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
- python实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
queue = [[root.left, root.right]]
while queue:
element = queue.pop(0)
root.left = element[0]
root.right = element[1]
if root.left == None and root.right == None:
continue
if root.left == None or root.right == None:
return False
if root.left.val != root.right.val:
return False
queue.append([root.left.left, root.right.right])
queue.append([root.left.right, root.right.left])
return True# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
queue = [[root.left, root.right]]
while queue:
element = queue.pop(0)
root.left = element[0]
root.right = element[1]
if root.left == None and root.right == None:
continue
if root.left == None or root.right == None:
return False
if root.left.val != root.right.val:
return False
queue.append([root.left.left, root.right.right])
queue.append([root.left.right, root.right.left])
return True
- c 实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool check(TreeNode* u, TreeNode* v)
{
queue<TreeNode*> q;
q.push(u);
q.push(v);
while(!q.empty())
{
u = q.front();
q.pop();
v = q.front();
q.pop();
if(!u && !v)
{
continue;
}
if(!u || !v || (u->val != v->val))
{
return false;
}
q.push(u->left);
q.push(v->right);
q.push(u->right);
q.push(v->left);
}
return true;
}
bool isSymmetric(TreeNode* root) {
if(root==nullptr)
{
return true;
}
return check(root, root);
}
};
170 二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
提示：
- 树中的节点数为
n。 1 <= k <= n <= 1040 <= Node.val <= 104
进阶： 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
解题思路：
基于二叉搜索树的性质，二叉搜索树的中序遍历左根右是一个有序序列。因此先中序遍历，找到第k个小的元素即可。中序遍历的方式有递归和迭代，这里使用迭代的方式，就不需要遍历完整个树后，再去遍历序列找第k小的元素。
- python实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if k == 0:
return root.val
root = root.right
- c 实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> stk;
while(root != nullptr || !stk.empty())
{
while(root != nullptr)
{
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
k--;
if(k==0)
{
break;
}
root = root->right;
}
return root->val;
}
};
进阶
如果二叉搜索树经常被修改，这个时候就需要记录子树的结点数。
在方法一中，我们之所以需要中序遍历前 个元素，是因为我们不知道子树的结点数量，不得不通过遍历子树的方式来获知。因此，可以记录下以每个结点为根结点的子树的结点数，并在查找第 小的值时，使用如下方法搜索：
- 令
node等于根结点，开始搜索。 - 对当前结点
node进行如下操作：- 如果
node的左子树的结点数left小于k-1，则第k小的元素一定在node的右子树中，令node等于其的右子结点，k等于k-left-1，并继续搜索； - 如果
node的左子树的结点数lelft等于k-1，则第k小的元素即为node，结束搜索并返回node即可； - 如果
node的左子树的结点数left大于k-1，则第 小的元素一定在node的左子树中，令node等于其左子结点，并继续搜索。
- 如果
在实现中，既可以将以每个结点为根结点的子树的结点数存储在结点中，也可以将其记录在哈希表中。
- python实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
bst = MyBst(root)
return bst.kth_smallest(k)
class MyBst:
def __init__(self, root):
self.root = root
self._node_num = {}
self._count_node_num(root)
def kth_smallest(self, k: int):
node = self.root
while node:
left = self._get_node_num(node.left)
if left < k-1: # 在右边
node = node.right
k -= left 1
elif left == k-1:
return node.val
else:
node = node.left # 在左边
def _count_node_num(self, node):
if not node:
return 0
self._node_num[node] = 1 self._count_node_num(node.left) self._count_node_num(node.right)
return self._node_num[node]
def _get_node_num(self, node):
return self._node_num[node] if node in self._node_num else 0
- c 实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class MyBst {
public:
MyBst(TreeNode *root) {
this->root = root;
countNodeNum(root);
}
// 返回二叉搜索树中第k小的元素
int kthSmallest(int k) {
TreeNode *node = root;
while (node != nullptr) {
int left = getNodeNum(node->left);
if (left < k - 1) {
node = node->right;
k -= left 1;
} else if (left == k - 1) {
break;
} else {
node = node->left;
}
}
return node->val;
}
private:
TreeNode *root;
unordered_map<TreeNode *, int> nodeNum;
// 统计以node为根结点的子树的结点数
int countNodeNum(TreeNode * node) {
if (node == nullptr) {
return 0;
}
nodeNum[node] = 1 countNodeNum(node->left) countNodeNum(node->right);
return nodeNum[node];
}
// 获取以node为根结点的子树的结点数
int getNodeNum(TreeNode * node) {
if (node != nullptr && nodeNum.count(node)) {
return nodeNum[node];
}else{
return 0;
}
}
};
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
MyBst bst(root);
return bst.kthSmallest(k);
}
};
