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

在一棵 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 的有序性，这份解法压根没用上，它对任意二叉树都成立。

Python

from __future__ import annotations
from 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 = right
class 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 = right
class 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)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        unordered_set<int> vis;

        function<bool(TreeNode*)> dfs = [&](TreeNode* root) {
            if (!root) {
                return false;
            }
            if (vis.count(k - root->val)) {
                return true;
            }
            vis.insert(root->val);
            return dfs(root->left) || dfs(root->right);
        };
        return dfs(root);
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private Set<Integer> vis = new HashSet<>();
    private int k;

    public boolean findTarget(TreeNode root, int k) {
        this.k = k;
        return dfs(root);
    }

    private boolean dfs(TreeNode root) {
        if (root == null) {
            return false;
        }
        if (vis.contains(k - root.val)) {
            return true;
        }
        vis.add(root.val);
        return dfs(root.left) || dfs(root.right);
    }
}