《剑指 Offer》专项突破版 - 面试题 56 : 二叉搜索树中两节点的值之和（详解 C++ 实现的两种方法）-尧图网站建设

前言

一、利用哈希表

二、应用双指针

前言

题目链接：LCR 056. 两数之和 IV - 输入二叉搜索树 - 力扣（LeetCode）

题目：

给定一棵二叉搜索树和一个值 k，请判断该二叉搜索树中是否存在值之和等于 k 的两个节点。假设二叉搜索树中节点的值均唯一。例如，在下图所示的二叉搜索树中，存在值之和等于 12 的两个节点（节点 5 和节点 7），但不存在值之和为 22 的两个节点。

分析：

解决这个问题自然需要遍历二叉树中的所有节点，因此这是一个关于二叉树遍历的问题。

一、利用哈希表

解决这个问题最直观的思路是利用哈希表保存节点的值。可以采用任意遍历算法遍历输入的二叉搜索树，每遍历到一个节点（节点的值记为 v），就在哈希表中查找是否存在值为 k - v 的节点。如果存在就表示存在值之和等于 k 的两个节点。

class Solution {
public:bool findTarget(TreeNode* root, int k) {unordered_set<int> us;stack<TreeNode*> st;TreeNode* cur = root;while (cur || !st.empty()){while (cur){st.push(cur);cur = cur->left;}
cur = st.top();st.pop();if (us.count(k - cur->val)){return true;}else{us.insert(cur->val);}cur = cur->right;}return false;}
};

假设二叉搜索树中节点的数目是 n，树的深度为 h。上述代码由于需要遍历二叉搜索树，因此时间复杂度是 O(n)。该算法除了需要一个大小为 O(h) 的栈保存朝着指向左子节点的指针经过的所有节点，还需要一个大小为 O(n) 的哈希表保存节点的值，因此总的空间复杂度是 O(n)。

上述算法其实适合任何二叉树，并没有利用二叉搜索树的特性，接下来根据二叉搜索树的特性做进一步的优化。

二、应用双指针

面试题 6 介绍了如何利用双指针判断在排序数组中是否包含两个和为 k 的数字，即把第 1 个指针指向数组的第 1 个（也是最小的）数字，把第 2 个指针指向数组的最后一个（也是最大的）数字。如果两个数字之和等于 k，那么就找到了两个符合要求的数字；如果两个数字之和大于 k，那么向左移动第 2 个指针使它指向更小的数字；如果两个数字之和小于 k，那么向右移动第 1 个指针使它指向更大的数字。

实际上，在某种程度上可以把二叉搜索树看成一个排序的数组，因为按照中序遍历的顺序将得到一个递增的序列。如果采用面试题 55 中的 BSTIterator，则可以每次按照从小到大的顺序从二叉树中取出一个节点。此时 BSTIterator 相当于解决面试题 6 中的第 1 个指针。

第 2 个指针应该每次按照从大到小的顺序从二叉搜索树中取出一个节点。受面试题 54 的启发，如果交换中序遍历算法中的指向左右子节点的指针，就可以实现按照从大到小的顺序遍历二叉搜索树。因此，可以采用类似的思路实现一个颠倒顺序的二叉搜索树的迭代器，如下所示：

class ReversedBSTIterator {
public:ReversedBSTIterator(TreeNode* root) : cur(root) {}
int prev() {while (cur){st.push(cur);cur = cur->right;}cur = st.top();st.pop();int result = cur->val;cur = cur->left;return result;}
bool hasPrev() {return cur || !st.empty();}
private:stack<TreeNode*> st;TreeNode* cur;
};

有了 ReversedBSTIterator 迭代器，每次调用函数 prev 都将按照从大到小的顺序从二叉搜索树中取出一个节点的值。

有了这两个迭代器之后，就很容易地运用双指针的思路，其参考代码如下所示：

class Solution {
public:bool findTarget(TreeNode* root, int k) {if (root == nullptr)return false;
BSTIterator it(root);ReversedBSTIterator rit(root);int next = it.next();int prev = rit.prev();while (next != prev){int sum = next + prev;if (sum < k)next = it.next();else if (sum > k)prev = rit.prev();elsereturn true;}return false;}
};

这两个迭代器一起使用可能需要遍历整棵二叉搜索树，因此时间复杂度是 O(n)。每个迭代器都需要一个大小为 O(h) 的栈，因此总的空间复杂度是 O(h)。在大多数情况下，二叉树的深度远小于二叉树的节点数，因此第 2 种算法的总体空间效率要优于第 1 种算法。

资讯详情

《剑指 Offer》专项突破版 - 面试题 56 : 二叉搜索树中两节点的值之和（详解 C++ 实现的两种方法）

前言

一、利用哈希表

二、应用双指针