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

记住这句「先查 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 有序能换来双指针解法，是这题的进阶点。