1 算法题 ：使用二叉树的数据结构在无序数组中查找指定元素
1.1 题目含义
这个题目的含义是首先根据一个无序数组来构建一个二叉搜索树（BST）。在构建好二叉搜索树之后，需要在树中查找指定的元素，并返回这个元素在原始无序数组中的位置（即索引）。这要求不仅要实现二叉搜索树的构建和查找功能，还要能够在树中的节点和原始数组的元素之间建立映射关系，以便能够准确地返回元素在数组中的位置。
需要注意的是，由于数组是无序的，因此在构建二叉搜索树时，需要根据数组中的元素值来确定它们在树中的位置，而不是根据它们在数组中的顺序。此外，由于数组中可能存在重复的元素，需要确定如何处理这种情况。例如，可以选择返回找到的第一个匹配元素在数组中的位置，或者返回所有匹配元素位置的列表。在本题中，只需要返回找到的第一个匹配元素的位置。
1.2 示例
示例 1:
输入：
- nums = [4, 2, 7, 10, 1, 6, 8]
- target = 7
输出：
- 2
说明：
- 首先，根据数组 [4, 2, 7, 10, 1, 6, 8] 构建一个二叉搜索树。然后，在树中查找元素 7。找到后，返回元素 7 在原始数组中的位置，即索引 2。
示例 2:
输入：
- nums = [1, 3, 5, 7]
- target = 9
输出：
- -1
说明：
- 根据数组 [1, 3, 5, 7] 构建二叉搜索树后，在树中查找元素 9。由于元素 9 不存在于树中，所以返回 -1，表示未找到目标值。
示例 3:
输入：
- nums = []
- target = 0
输出：
- -1
说明：
- nums 为空，0 不存在于 nums 中，返回 -1。
2 解题思路
这一题目涉及两个主要步骤：BST 的构建和 BST 中的元素查找，以及如何在 BST 节点和原始数组元素之间建立并维护索引映射关系。
BST 构建与查找基础
二叉搜索树是一种特殊的二叉树，其每个节点的值都大于其左子树中任意节点的值，且小于其右子树中任意节点的值。这种特性使得 BST 在元素查找、插入和删除操作中具有高效的性能，时间复杂度通常为 O(log n)，其中n为树中节点的数量。
在 BST 中查找元素时，通常从根节点开始，将目标值与当前节点的值进行比较。如果目标值小于当前节点的值，则在左子树中继续查找；如果目标值大于当前节点的值，则在右子树中继续查找；如果两者相等，则找到了目标元素。
解题思路详解
（1）构建 BST
选择根节点
- 对于无序数组，可以选择数组中间的元素作为根节点，这样可以尽量保证树的平衡，减少树的高度，从而提高查找效率。这通常通过快速选择算法或排序后选择中间元素实现。
递归构建子树
- 一旦选择了根节点，将原始数组划分为两部分：小于根节点的元素集合和大于根节点的元素集合。这两部分将分别作为根节点的左子树和右子树。
递归地对这两个子数组执行相同的操作，即选择子数组的中间元素作为子树的根节点，并继续划分和构建。
处理特殊情况
- 如果数组为空或只有一个元素，则该元素本身就是BST的根节点，无需进一步划分。
- 在递归过程中，需要确保数组划分的正确性，避免重复或遗漏元素。
（2）维护索引映射
由于题目要求返回元素在原始数组中的位置，需要在构建 BST 的过程中维护一个索引映射关系。这可以通过以下几种方式实现：
- 使用哈希表：在构建BST的同时，使用一个哈希表（如 std::unordered_map）来存储每个节点值与原始数组索引的对应关系。每当向 BST 中插入一个新节点时，都将该节点的值与它在原始数组中的索引添加到哈希表中。这样，在查找元素时，一旦在 BST 中定位到目标节点，就可以通过哈希表迅速获取该节点值在原始数组中的索引。
- 使用数组或向量：另一种方法是使用一个与原始数组等长的数组或向量来存储索引信息。在构建 BST 的过程中，每当插入一个节点时，都更新该节点值对应位置上的索引值。
这种方法的好处是空间效率较高，但缺点是当 BST 中的节点值与原始数组中的元素不完全对应时（例如，存在重复元素或某些元素未被插入到 BST 中），可能需要额外的逻辑来处理未使用的索引位置。
（3）在BST中查找元素
- 从根节点开始查找：查找操作从BST的根节点开始，将目标值与当前节点的值进行比较。
- 递归查找：如果目标值小于当前节点的值，则递归地在左子树中查找；如果目标值大于当前节点的值，则递归地在右子树中查找。如果找到了与目标值相等的节点，则通过之前维护的索引映射关系获取该节点在原始数组中的索引。
- 处理未找到的情况：如果在BST中未找到目标值，则返回-1或其他表示未找到的标识符。
（4）优化与注意事项
- 平衡BST：为了提高BST的性能，尤其是当输入数组本身有序或接近有序时，可以考虑使用平衡BST的变种，如AVL树或红黑树。这些数据结构在插入和删除节点时会自动调整树的结构，以保持较好的平衡性。
- 处理重复元素：如果原始数组中存在重复元素，需要明确题目要求返回哪个位置的索引（例如，返回第一个匹配元素的索引）。这可能需要在构建BST和维护索引映射时采用特定的策略。
- 空间复杂度：除了BST本身占用的空间外，还需要考虑维护索引映射所需的空间。使用哈希表通常具有较好的时间复杂度，但可能增加空间复杂度；而使用数组或向量则可以在空间上更紧凑，但可能需要额外的逻辑来处理未使用的索引位置。
- 错误处理与边界情况：在实现过程中，需要注意处理各种错误处理和边界情况，确保代码的健壮性和正确性。例如，当输入数组为空时，应直接返回 -1 表示未找到元素；当目标值不在 BST 的值域范围内时，也应快速返回 -1。
3 算法实现代码
如下为算法实现代码：
#include <iostream>
#include <vector>
#include <unordered_map>
#include <memory>
#include <algorithm>
// BST节点的定义
struct TreeNode {
int val;
int originalIndex; // 原始数组中的索引
std::shared_ptr<TreeNode> left;
std::shared_ptr<TreeNode> right;
TreeNode(int x) : val(x), originalIndex(-1), left(nullptr), right(nullptr) {}
};
class Solution
{
public:
// 查找元素的函数
int findElement(const std::vector<int>& nums, int target) {
if (nums.empty()) {
return -1;
}
std::unordered_map<int, int> indexMap; // 用于维护索引映射的哈希表
for (int i = 0; i < nums.size(); i++)
{
indexMap.insert(std::make_pair(nums[i], i));
}
std::vector<int> sortedNums = nums;
std::sort(sortedNums.begin(), sortedNums.end());
// 构建BST
std::shared_ptr<TreeNode> root = buildBST(sortedNums, 0, sortedNums.size() - 1);
int index = findElementInBST(root, target);
if (index>=0) {
return indexMap.find(sortedNums[index])->second;
}
else
{
return -1;
}
}
private:
// 在BST中查找元素的函数
int findElementInBST(std::shared_ptr<TreeNode> root, int target) {
if (root == nullptr) {
return -1;
}
if (root->val == target) {
return root->originalIndex; // 返回目标元素在原始数组中的索引
}
else if (target < root->val) {
return findElementInBST(root->left, target); // 在左子树中查找
}
else {
return findElementInBST(root->right, target); // 在右子树中查找
}
}
// 构建BST的函数
std::shared_ptr<TreeNode> buildBST(const std::vector<int>& nums, int start, int end) {
if (start > end) {
return nullptr;
}
int mid = start + (end - start) / 2;
std::shared_ptr<TreeNode> root = std::make_shared<TreeNode>(nums[mid]);
root->originalIndex = mid; // 设置根节点的原始索引
root->left = buildBST(nums, start, mid - 1); // 递归构建左子树
root->right = buildBST(nums, mid + 1, end); // 递归构建右子树
return root;
}
};
上面示例先对数组进行排序，然后使用中序遍历来构建BST。如果直接根据无序数组构建BST（而不是平衡BST或排序数组对应的BST），那么构建过程将变得复杂，因为需要某种策略来选择根节点，并递归地处理剩余元素。一种简单的方法是随机选择根节点，但这通常不会得到平衡的BST。
注意，上述代码使用了智能指针做内存管理，如果使用原始指针，则还需要实现一个递归函数来遍历整个 BST 并删除每个节点，以避免内存泄漏。这通常是通过后序遍历（先左子树，再右子树，最后根节点）来实现的，并在每个节点上调用 delete 操作符。
调用上面的算法，并得到输出：
int main()
{
Solution s;
std::vector<int> nums = { 5, 15, 25, 35, 45, 10, 20, 30, 40, 50 }; // 示例无序数组
// 查找元素
int target = 35; // 要查找的目标元素
int index = s.findElement(nums, target);
// 输出结果
if (index != -1) {
std::cout << "Element " << target << " found at index " << index << " in the original array." << std::endl;
}
else {
std::cout << "Element " << target << " not found in the BST." << std::endl;
}
return 0;
}
上面代码的输出为：
Element 35 found at index 3 in the original array.
4 测试用例
以下是针对上面算法的测试用例，基本覆盖了各种情况：
（1）基础测试用例
输入：数组 [3, 5, -1, 0, 9, 12]，目标值 9
输出：4
说明：目标值 9 存在于数组中，位于索引 4 的位置。
（2）目标值不存在于数组中
输入：数组 [3, 5, -1, 0, 9, 12]，目标值 2
输出：-1
说明：目标值 2 不存在于数组中。
（3）目标值位于数组开头
输入：数组 [-1, 0, 3, 9, 5, 12]，目标值 -1
输出：0
说明：目标值 -1 位于数组的开头，即索引 0 的位置。
（4）目标值位于数组末尾
输入：数组 [9, -1, 3, 0, 5, 12]，目标值 12
输出：5
说明：目标值 12 位于数组的末尾，即索引 5 的位置。
（5）目标值位于数组中间
输入：数组 [0, -1, 3, 9, 5, 12]，目标值 3
输出：2
说明：目标值 3 位于数组的中间位置，即索引 2 的位置。
（6）空数组
输入：数组 []，目标值 9
输出：-1
说明：空数组不包含任何元素，因此无法找到目标值。
（7）数组只有一个元素
输入：数组 [9]，目标值 9
输出：0
说明：数组只有一个元素，且该元素就是目标值，位于索引 0 的位置。
（8）数组中存在多个相同的目标值
输入：数组 [1, 2, 3, 3, 4, 5]，目标值 3
输出：2 或 3
说明：数组中存在多个目标值 3，返回任意一个目标值的索引都是正确的。这里可以返回 2 或 3。
