LeetCode653 两数之和 -输入二叉搜索树

探索二叉搜索树中的两数之和问题

在算法和数据结构的领域中，二叉搜索树（Binary Search Tree，BST）是一种非常重要的数据结构。它具有一些特殊的性质，使得我们可以高效地进行查找、插入和删除等操作。今天，我们来探讨一个与二叉搜索树相关的有趣问题：给定一个二叉搜索树 root 和一个目标结果 k，判断二叉搜索树中是否存在两个元素，它们的和等于给定的目标结果 k。如果存在，返回 true；否则，返回 false。

一、二叉搜索树的特性回顾

二叉搜索树是一种有序的二叉树，对于树中的每个节点，其左子树的所有节点的值都小于该节点的值，而右子树的所有节点的值都大于该节点的值。这种特性使得二叉搜索树在很多算法问题中都有着独特的应用。

二、解题思路与实现

（一）中序遍历 + 双指针法

思路：
- 首先，我们知道二叉搜索树的中序遍历结果是一个有序的序列。所以，我们可以通过中序遍历将二叉搜索树的所有节点值存储到一个数组中。
- 然后，利用双指针法，在这个有序数组中查找是否存在两个数的和等于目标值 k。我们设置一个左指针 left 指向数组的起始位置，一个右指针 right 指向数组的末尾位置。
- 接着，通过比较 arr[left] + arr[right] 与 k 的大小关系来移动指针。如果和等于 k，则找到了符合条件的两个数；如果和小于 k，则将左指针右移一位，以增大和的值；如果和大于 k，则将右指针左移一位，以减小和的值。重复这个过程，直到左指针和右指针相遇。
C 语言实现代码：

#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点结构体
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};// 中序遍历二叉树，将节点值存入数组，并返回数组大小
int inorderTraversal(struct TreeNode* root, int* arr, int* index) {if (root == NULL) {return 0;}int leftCount = inorderTraversal(root->left, arr, index);arr[(*index)++] = root->val;int rightCount = inorderTraversal(root->right, arr, index);return leftCount + 1 + rightCount;
}// 函数用于判断二叉搜索树中是否存在两数之和等于目标值k
bool findTarget(struct TreeNode* root, int k) {int arrSize = 1000;  // 预先分配一定大小的数组空间，可根据实际情况调整或优化动态分配策略int* arr = (int*)malloc(arrSize * sizeof(int));if (arr == NULL) {printf("内存分配失败！\n");return false;}int index = 0;int count = inorderTraversal(root, arr, &index);int left = 0;int right = count - 1;while (left < right) {int sum = arr[left] + arr[right];if (sum == k) {free(arr);return true;} else if (sum < k) {left++;} else {right--;}}free(arr);return false;
}

复杂度分析：
- 时间复杂度：中序遍历二叉树的时间复杂度为 $O(n)$ ，其中 n 是二叉树节点的个数。后续在有序数组上使用双指针法查找的时间复杂度也是 $O(n)$ 。所以总的时间复杂度为 $O(n)$ 。
- 空间复杂度：主要的空间消耗在于存储中序遍历结果的数组，在最坏情况下（二叉树是一条链时），数组长度为 n，所以空间复杂度是 $O(n)$ 。此外，递归调用栈在最坏情况下也会达到 $O(n)$ 的深度，综合来看空间复杂度是 $O(n)$ 。

（二）哈希表法

思路：
- 我们可以使用哈希表来记录已经遍历过的节点值。在遍历二叉搜索树的过程中，对于每个节点，计算其与目标值 k 的差值 target = k - node->val。
- 然后，在哈希表中查找是否存在这个差值。如果存在，说明找到了两个节点值之和等于 k；如果不存在，则将当前节点值插入到哈希表中，继续遍历下一个节点。
C 语言实现代码（借助 uthash 库）：

#include <stdio.h>
#include <stdlib.h>
#include "uthash.h"// 定义二叉树节点结构体
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};// 定义哈希表节点结构体
struct HashNode {int key;UT_hash_handle hh;
};// 函数用于判断二叉搜索树中是否存在两数之和等于目标值k
bool findTarget(struct TreeNode* root, int k) {struct HashNode* hashTable = NULL;struct TreeNode* stack[100];  // 简单用数组模拟栈，可根据实际情况调整大小int top = -1;while (root!= NULL || top >= 0) {while (root!= NULL) {stack[++top] = root;root = root->left;}root = stack[top--];int target = k - root->val;struct HashNode* find;HASH_FIND_INT(hashTable, &target, find);if (find!= NULL) {return true;}// 将当前节点值加入哈希表struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));newNode->key = root->val;HASH_ADD_INT(hashTable, key, newNode);root = root->right;}return false;
}

复杂度分析：
- 时间复杂度：遍历二叉搜索树的每个节点，对于每个节点在哈希表中查找和插入操作的平均时间复杂度都接近常数，所以总的时间复杂度是 $O(n)$ ，其中 n 是二叉树节点的个数。
- 空间复杂度：哈希表中最多会存储 n 个不同的节点值，所以空间复杂度是 $O(n)$ 。