如何判断二叉搜索树中是否存在两个节点之和等于目标值？

简化版

可以把 BST 中序遍历成有序数组，再用双指针判断是否存在两数之和等于目标值。也可以 DFS 遍历时用 HashSet 记录已见值，检查 target - node.val 是否出现过。

详细版

BST 的中序遍历天然有序，所以最直接做法是：

中序遍历得到升序数组 arr；
左指针 l=0，右指针 r=n-1；
若 arr[l]+arr[r]==target，返回 true；
若和太小，说明需要更大值，l++；
若和太大，说明需要更小值，r--；
指针相遇仍未找到，返回 false。

时间复杂度 O(n)，空间复杂度 O(n)。如果不想显式保存数组，可以用两个迭代器分别做正向中序和反向中序，空间降到 O(h)，但实现更复杂。

HashSet 做法同样是 O(n)：遍历每个节点时先看集合里有没有 target - val，没有就把当前值放进去。它不利用 BST 有序性，但代码短，适合普通二叉树。

完整版教学

一、为什么这题要先想到中序遍历

BST 最大的结构红利是「左子树 < 根 < 右子树」。如果按中序遍历访问节点，访问顺序就是升序，这等价于把树问题转换成一个经典有序数组的 Two Sum。很多同学一看到树就下意识递归暴搜，但这题的目标不是遍历本身，而是判断两个值能否配成目标和。利用有序性后，每次指针移动都能排除一整批不可能组合。

例如中序数组是 [2,3,4,5,7,9]，目标是 12。初始 2+9=11 太小，此时 2 和任何不超过 9 的数相加都不会超过 11，所以 2 不可能作为答案左端，左指针可以安全右移。这就是双指针正确性的核心，而不是机械地背 l++/r--。

记忆钩子：BST 的中序遍历不是「多一种遍历方式」，而是把树摊平成有序数组；一旦有序，Two Sum 就从暴力枚举变成双指针收缩。

二、双指针为什么不会漏答案

双指针维护的是一个候选区间 [l,r]。当 arr[l]+arr[r] < target 时，即使用当前最右侧最大值都不够，说明 arr[l] 与区间内任何值相加都不可能达到 target，因此可以丢弃 arr[l]。当 arr[l]+arr[r] > target 时，即使用当前最左侧最小值都太大，说明 arr[r] 与区间内任何值相加都会偏大，因此可以丢弃 arr[r]。

看一个带数字的推演：

arr = [1, 4, 6, 8, 10, 13], target = 14
l=0,r=5: 1+13=14，命中

arr = [1, 4, 6, 8, 10, 13], target = 17
l=0,r=5: 1+13=14 < 17，丢弃 1
l=1,r=5: 4+13=17，命中

这里每一步都不是猜，而是基于有序数组的单调性做排除。只要数组严格升序或非降序，逻辑都成立；BST 若允许重复值，也要注意不能让同一个节点被用两次。

三、代码实现怎么写更稳

最稳的面试写法是「中序 + 双指针」。它把两个逻辑拆开：先保证有序，再判断两数之和，代码可读性很好。实现时要注意中序递归可能有栈空间 O(h)，数组占 O(n)。

boolean findTarget(TreeNode root, int k) {
    List<Integer> nums = new ArrayList<>();
    inorder(root, nums);
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int sum = nums.get(l) + nums.get(r);
        if (sum == k) return true;
        if (sum < k) l++;
        else r--;
    }
    return false;
}

void inorder(TreeNode node, List<Integer> nums) {
    if (node == null) return;
    inorder(node.left, nums);
    nums.add(node.val);
    inorder(node.right, nums);
}

如果节点值可能很大，sum 可以用 long，避免 int 溢出。题目通常给出安全范围，但工程代码里这个细节值得主动提一句。

四、HashSet 解法和 BST 解法怎么选

HashSet 解法不需要 BST 性质，只要遍历到一个值 x，检查 k-x 是否出现过即可。它的好处是实现短，且适用于任意二叉树；缺点是没利用有序性，空间 O(n)。中序双指针也需要 O(n) 数组，但它展示了你知道 BST 的关键性质。

解法	是否利用 BST	时间	空间	适合场景
DFS + HashSet	否	O(n)	O(n)	任意二叉树、快速写出
中序数组 + 双指针	是	O(n)	O(n)	面试展示 BST 性质
双迭代器	是	O(n)	O(h)	追求额外空间更低

如果面试官问优化空间，就引出正向迭代器和反向迭代器。两者分别模拟升序和降序遍历，像数组双指针一样向中间靠拢。

五、双迭代器为什么能把空间降到 O(h)

中序数组一次性保存全部 n 个节点，空间是 O(n)。但双指针真正需要的只是「当前最小候选」和「当前最大候选」，以及继续前进时的路径栈。因此可以维护两个栈：一个不断取下一个升序值，一个不断取下一个降序值。

对于高度为 h 的树，每个栈最多保存一条从根到叶的路径，所以空间 O(h)。平衡树时 h≈log n，退化链表时 h≈n。这个优化的代价是代码明显更长，还要确保两个迭代器没有指向同一个节点，而不是只比较值。

nextSmall: left spine -> 当前最小 -> 右子树左链
nextLarge: right spine -> 当前最大 -> 左子树右链

面试中先写数组版通常更稳，再主动说明空间可优化到 O(h)，会比一上来写复杂迭代器更不容易出错。

六、边界情况如何处理

空树或只有 1 个节点时一定返回 false，因为题目要求两个节点。双指针循环必须是 l < r，不能写成 l <= r，否则会把同一个节点用两次。HashSet 版本必须先查 complement，再加入当前值；如果先加入当前值，目标为 2*x 时会错误命中自己。

还有一个容易忽略的边界是重复值。如果 BST 允许两个不同节点值都为 5，目标为 10 是可以成立的；数组双指针用下标区分节点，没问题。HashSet 若用值集合，也能在第二个 5 到来时命中第一个 5；关键仍然是先查再加。

七、常见误区与追问

误区：BST 两数之和必须用递归暴力枚举。 暴力对每个节点再查另一个值可做到 O(nh)，但没有中序双指针清晰。
追问：为什么 l < r 不能写成 l <= r？ 因为同一个节点不能使用两次，指针相等代表已经是同一个数组元素。
误区：HashSet 解法一定比中序双指针更差。 它只是没有利用 BST 有序性，但时间仍是 O(n)，在普通二叉树场景反而更通用。
追问：如何把空间从 O(n) 降到 O(h)？ 用正向中序迭代器和反向中序迭代器，只保存两条路径栈。
误区：比较两个迭代器当前值不同就代表节点不同。 BST 可能有重复值，严谨实现应比较节点引用是否相同。

八、加强记忆

这题可以记成「BST 先中序，Two Sum 用双指针」。中序把树的结构优势变成数组的有序性；双指针利用单调性，每次根据和偏小或偏大排除一个端点。HashSet 是通用解，数组双指针是 BST 特色解，双迭代器是空间优化解。真正面试时先把正确性讲清楚：和太小丢左端，因为左端配最大值都不够；和太大丢右端，因为右端配最小值都太大。

简化版

详细版