题目描述
思路解析
一句话答案：LeetCode 653 两数之和 IV·输入 BST：判断二叉搜索树里有没有两个不同节点，值之和为 k。参考解把它当普通两数之和做——DFS 边走边查 k 减当前值在不在哈希集合里，在就返 true，时间 O(n)。
在一棵 BST 里凑出和为 k 的两个节点
给一棵二叉搜索树 root，也就是左小右大的那种树，再给一个目标整数 k。问树里存不存在两个不同的节点，值加起来正好等于 k，存在返回 true，否则返回 false。题面例子 root=[50,30,80,20,40,null,90]、k 为 140，其中 50 加 90 等于 140，返回 true；把 k 换成 200，任何两个节点都凑不出，返回 false。
暴力两两配对为什么拖不动
把任意两个节点凑成一对、挨个验和是最直白的路子：外层选定一个节点，内层再扫整棵树找它的搭档。n 个节点这样要比 n 乘 n 次，也就是 O(n²)，节点一多就拖不动。真正费时的是内层那一趟——为了确认一个节点有没有搭档，把整棵树重新翻了一遍。
把它看成普通两数之和
跳出 BST，这题的骨架和数组版两数之和一模一样：要凑和为 k 的两个数，走到当前值时，它要找的搭档其实唯一确定，就是补数 k 减当前值。与其回头再扫一遍找补数，不如备一个哈希集合，也就是能在 O(1) 时间查一个值在不在的容器，把走过的节点值都记进去。参考代码正是拿一个集合 vis，按 DFS 先序，也就是先处理自己再往左右子树下钻，走一遍，全程没碰 BST 左小右大的性质。
每到一个节点，先查补数再存自己
递归函数 dfs 在每个节点只做三件事：空节点直接返回 false；否则先算补数 k 减当前值，去 vis 里查，查到就一路返回 true；没查到，才把当前值 add 进 vis，再递归左、右子树，两边任一为真就为真。这个顺序是硬要求，必须先查后存。若反过来先把自己塞进集合再查补数，遇到 k 恰好是当前值两倍时，会拿刚存进去的自己当搭档，把一个节点算成两个，答案就错了。先查后存保证查到的补数一定来自别的、更早走过的节点。
顺着 50、30、80 这棵树走一遍
k 为 140，vis 起初为空，先序顺序是 50、30、20、40、80、90。到 50：补数 140 减 50 等于 90，vis 空、没有，存入 50。到 30：补数 110，vis={50} 里没有，存入 30。到 20：补数 120，没有，存入 20。到 40：补数 100，没有，存入 40。到 80：补数 60，vis={50,30,20,40} 里没有，存入 80。到 90：补数 140 减 90 等于 50，而 vis={50,30,20,40,80} 里真有 50——它是根节点早先留下的，50 加 90 等于 140，返回 true，后面的节点不用再看。
一遍走完的代价与两个边界
每个节点只访问一次，查补数和插入集合都是均摊 O(1)，所以时间 O(n)，n 是节点数；空间上集合最多存 n 个值，递归栈在最坏退化成一条链时也是 O(n)。另有两点容易漏。只有一个节点时永远返回 false，因为要凑的是两个不同节点；先查后存的顺序一旦写反，就会让节点自己和自己配对。至于 BST 的有序性，这份解法压根没用上，它对任意二叉树都成立。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句「先查 k 减 v 在不在集合里，不在就把 v 存进去」，下面每一帧都在套它。
准备 · 目标 k = 140：先看全局：目标 k 等于 140，手里准备一个空的哈希集合 vis，用来记「一路上见过的节点值」。我们从根节点 50 出发，按先序一个一个走，每到一个节点都做同一件事：查搭档、不在就存。
对照 · 笨办法两两配对：先想最直白的笨办法：把任意两个节点都配一遍，看哪一对加起来等于 140。这样要嵌套两层、共 n 乘 n 次，节点一多就慢。下面这套哈希集合法只走一遍，就能把它降到线性，注意看差别。
走到节点 50：DFS 走到节点 50（紫色）。按套路，先别急着把它存进集合，要先问一句：谁和它搭档能凑成 140？那个搭档就是 140 减 50 等于 90。
查集合 · 找 90：去集合里查搭档 90：当前集合是 {（空）}，翻一遍，里面没有 90。这一步只花常数时间，不用再去扫别的节点。
存入 50：既然没配上，就把 50 自己记进集合（节点变蓝表示已记下），留给后面还没走到的节点来配。集合现在是 {50}，继续按先序往下走。
走到节点 30：DFS 走到节点 30（紫色）。按套路，先别急着把它存进集合，要先问一句：谁和它搭档能凑成 140？那个搭档就是 140 减 30 等于 110。
查集合 · 找 110：去集合里查搭档 110：当前集合是 {50}，翻一遍，里面没有 110。这一步只花常数时间，不用再去扫别的节点。
存入 30：既然没配上，就把 30 自己记进集合（节点变蓝表示已记下），留给后面还没走到的节点来配。集合现在是 {50，30}，继续按先序往下走。
走到节点 20：DFS 走到节点 20（紫色）。按套路，先别急着把它存进集合，要先问一句：谁和它搭档能凑成 140？那个搭档就是 140 减 20 等于 120。
查集合 · 找 120：去集合里查搭档 120：当前集合是 {50，30}，翻一遍，里面没有 120。这一步只花常数时间，不用再去扫别的节点。
存入 20：既然没配上，就把 20 自己记进集合（节点变蓝表示已记下），留给后面还没走到的节点来配。集合现在是 {50，30，20}，继续按先序往下走。
走到节点 40：DFS 走到节点 40（紫色）。按套路，先别急着把它存进集合，要先问一句：谁和它搭档能凑成 140？那个搭档就是 140 减 40 等于 100。
查集合 · 找 100：去集合里查搭档 100：当前集合是 {50，30，20}，翻一遍，里面没有 100。这一步只花常数时间，不用再去扫别的节点。
存入 40：既然没配上，就把 40 自己记进集合（节点变蓝表示已记下），留给后面还没走到的节点来配。集合现在是 {50，30，20，40}，继续按先序往下走。
走到节点 80：DFS 走到节点 80（紫色）。按套路，先别急着把它存进集合，要先问一句：谁和它搭档能凑成 140？那个搭档就是 140 减 80 等于 60。
查集合 · 找 60：去集合里查搭档 60：当前集合是 {50，30，20，40}，翻一遍，里面没有 60。这一步只花常数时间，不用再去扫别的节点。
存入 80：既然没配上，就把 80 自己记进集合（节点变蓝表示已记下），留给后面还没走到的节点来配。集合现在是 {50，30，20，40，80}，继续按先序往下走。
走到节点 90：DFS 走到节点 90（紫色）。按套路，先别急着把它存进集合，要先问一句：谁和它搭档能凑成 140？那个搭档就是 140 减 90 等于 50。
命中 · 50 在集合里：去集合里查搭档 50：集合 {50，30，20，40，80} 里真的有 50！它是之前走过的节点留下来的，现在 50 加 90 正好等于 140，配对成功。
配对成功 · 50 + 90 = 140：把这一对点亮：50 和 90（两个绿色节点）加起来正好是目标 140。一找到就可以直接返回 true，剩下的节点都不用再看了。
完成 · 返回 true：回看全程：我们只把每个节点访问了一遍，靠集合一路记搭档。走到 90 时，发现它要找的 50 早被记下了，于是 50 加 90 等于 140，答案 true。整棵树没有任何两两嵌套的配对，全程一遍走完。
单节点一定 false（要两个不同节点）。其余情形按「查补数」一遍走完即可判定。
面试高频追问：BST 有序能换来双指针解法，是这题的进阶点。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# 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 = rightclass Solution: def findTarget(self, root: Optional[TreeNode], k: int) -> bool: def dfs(root): if root is None: return False if k - root.val in vis: return True vis.add(root.val) return dfs(root.left) or dfs(root.right) vis = set() return dfs(root)复杂度
- 时间：O(n)，每个节点访问一次，集合查补数和插入都是均摊 O(1)，n 是节点总数
- 空间：O(n)，哈希集合最多存 n 个值；递归栈最坏 O(n)（退化成链），平衡时 O(log n)
易错点
面试追问把动画讲成自己的话
追问这道题是输入二叉搜索树，能不能利用「有序」这一点？
追问如果树非常大、不想占 O(n) 集合内存怎么办？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉搜索树节点最小距离
LeetCode 783 · 简单 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题