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

这道题到底在问什么

输入

root=[50,30,80,20,40,null,90], k=140

输出

true（50 加 90）

输入

同一棵树, k=200

输出

false

先想最直接的笨办法

先看全局：目标 k 等于 140，手里准备一个空的哈希集合 vis，用来记「一路上见过的节点值」。我们从根节点 50 出发，按先序一个一个走，每到一个节点都做同一件事：查搭档、不在就存。（动画第 4 步）

最优解：一步一步想明白

1. 3记住这句「先查 k 减 v 在不在集合里，不在就把 v 存进去」，下面每一帧都在套它。
2. 4集合为空先看全局：目标 k 等于 140，手里准备一个空的哈希集合 vis，用来记「一路上见过的节点值」。我们从根节点 50 出发，按先序一个一个走，每到一个节点都做同一件事：查搭档、不在就存。
3. 5两两枚举 O(n²)先想最直白的笨办法：把任意两个节点都配一遍，看哪一对加起来等于 140。这样要嵌套两层、共 n 乘 n 次，节点一多就慢。下面这套哈希集合法只走一遍，就能把它降到线性，注意看差别。
4. 6当前值 50DFS 走到节点 50（紫色）。按套路，先别急着把它存进集合，要先问一句：谁和它搭档能凑成 140？那个搭档就是 140 减 50 等于 90。
5. 790 不在去集合里查搭档 90：当前集合是 {（空）}，翻一遍，里面没有 90。这一步只花常数时间，不用再去扫别的节点。
6. 8集合 += 50既然没配上，就把 50 自己记进集合（节点变蓝表示已记下），留给后面还没走到的节点来配。集合现在是 {50}，继续按先序往下走。
7. 9当前值 30DFS 走到节点 30（紫色）。按套路，先别急着把它存进集合，要先问一句：谁和它搭档能凑成 140？那个搭档就是 140 减 30 等于 110。
8. 10110 不在去集合里查搭档 110：当前集合是 {50}，翻一遍，里面没有 110。这一步只花常数时间，不用再去扫别的节点。
9. 11集合 += 30既然没配上，就把 30 自己记进集合（节点变蓝表示已记下），留给后面还没走到的节点来配。集合现在是 {50，30}，继续按先序往下走。
10. 12当前值 20DFS 走到节点 20（紫色）。按套路，先别急着把它存进集合，要先问一句：谁和它搭档能凑成 140？那个搭档就是 140 减 20 等于 120。
11. 13120 不在去集合里查搭档 120：当前集合是 {50，30}，翻一遍，里面没有 120。这一步只花常数时间，不用再去扫别的节点。
12. 14集合 += 20既然没配上，就把 20 自己记进集合（节点变蓝表示已记下），留给后面还没走到的节点来配。集合现在是 {50，30，20}，继续按先序往下走。
13. 15当前值 40DFS 走到节点 40（紫色）。按套路，先别急着把它存进集合，要先问一句：谁和它搭档能凑成 140？那个搭档就是 140 减 40 等于 100。
14. 16100 不在去集合里查搭档 100：当前集合是 {50，30，20}，翻一遍，里面没有 100。这一步只花常数时间，不用再去扫别的节点。
15. 17集合 += 40既然没配上，就把 40 自己记进集合（节点变蓝表示已记下），留给后面还没走到的节点来配。集合现在是 {50，30，20，40}，继续按先序往下走。
16. 18当前值 80DFS 走到节点 80（紫色）。按套路，先别急着把它存进集合，要先问一句：谁和它搭档能凑成 140？那个搭档就是 140 减 80 等于 60。
17. 1960 不在去集合里查搭档 60：当前集合是 {50，30，20，40}，翻一遍，里面没有 60。这一步只花常数时间，不用再去扫别的节点。
18. 20集合 += 80既然没配上，就把 80 自己记进集合（节点变蓝表示已记下），留给后面还没走到的节点来配。集合现在是 {50，30，20，40，80}，继续按先序往下走。
19. 21当前值 90DFS 走到节点 90（紫色）。按套路，先别急着把它存进集合，要先问一句：谁和它搭档能凑成 140？那个搭档就是 140 减 90 等于 50。
20. 2250 已见过去集合里查搭档 50：集合 {50，30，20，40，80} 里真的有 50！它是之前走过的节点留下来的，现在 50 加 90 正好等于 140，配对成功。
21. 23答案 true把这一对点亮：50 和 90（两个绿色节点）加起来正好是目标 140。一找到就可以直接返回 true，剩下的节点都不用再看了。
22. 2450 + 90 = 140回看全程：我们只把每个节点访问了一遍，靠集合一路记搭档。走到 90 时，发现它要找的 50 早被记下了，于是 50 加 90 等于 140，答案 true。整棵树没有任何两两嵌套的配对，全程一遍走完。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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)

#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);
    }
};

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);
    }
}

复杂度

面试官可能追问