算法：搜索

用户3578099

发布于 2022-04-18 16:27:15

5670

发布于 2022-04-18 16:27:15

文章被收录于专栏：AI科技时讯AI科技时讯

搜索

搜索相关的问题，可以有两类任务，查找和遍历。

查找
- 二分搜索
- 顺序查找
- 二叉搜索树
- 无序查找
- 有序查找
遍历
- 深度优先遍历（栈的应用）
- 广度优先遍历（队列的应用）

查找

顺序搜索（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。

示例 :

输入: 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实现

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++实现

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 。

示例：

输入：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

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实现

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++实现

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：

输入：root = []
输出：[]

示例 3：

输入：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 <= 104
0 <= 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);
    }
};

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2022-03-25，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树