653. 两数之和 IV - 输入 BST

难度简单386收藏分享切换为英文接收动态反馈

给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

示例 1：

1
2
输入: root = [5,3,6,2,4,null,7], k = 9
输出: true

示例 2：

1
2
输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

提示:

  • 二叉树的节点个数的范围是 [1, 104].
  • -104 <= Node.val <= 104
  • root 为二叉搜索树
  • -105 <= k <= 105

题解：

解法1：DFS + 哈希表

通过DFS来遍历整棵树，用哈希表记录遍历过的结点值。

对于一个值为x的节点，只要检查哈希表中是否存在k - x即可。

如果找到存在对应的元素，则返回true。

否则，将当前结点值存入哈希表。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//深度优先搜索+哈希表
Set<Integer> set = new HashSet<>();

public boolean findTarget(TreeNode root, int k) {
    if (root == null) {
        return false;
    }
    //判断哈希表中是否含有对应元素
    if (set.contains(k - root.val)) {
        return true;
    }
    set.add(root.val);

    return findTarget(root.left, k) || findTarget(root.right, k);
}
  • 时间复杂度：O(N)，需要遍历整棵树
  • 空间复杂度：O(N)，最坏情况需要一个存储整棵树所有结点值的哈希表

解法2：BFS + 哈希表

原理同解法1，只是遍历方式不同

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public boolean findTarget(TreeNode root, int k) {

    if (root == null) {
        return false;
    }

    Queue<TreeNode> que = new ArrayDeque<>();
    que.offer(root);

    Set<Integer> set = new HashSet<>();


    while (!que.isEmpty()) {

        TreeNode node = que.poll();
        if (set.contains(k - node.val)) {
            return true;
        }
        set.add(node.val);

        //这里一定记住是当前节点node，不是root
        //错了好几次了
        if (node.left != null) {
            que.offer(node.left);
        }
        if (node.right != null) {
            que.offer(node.right);
        }


    }
    return false;

}
  • 时间复杂度：O(N)，需要遍历整棵树
  • 空间复杂度：O(N)，最坏情况需要一个存储整棵树所有结点值的哈希表和队列

解法3：DFS + 中序遍历 + 双指针

二叉搜索树的中序遍历结果是一个递增序列，可以遍历得到整棵树的结点值，然后使用双指针找到是否有两数之和等于目标值的元素。如果两数之和大于目标值，右指针左移；如果两数之和小于目标值，左指针右移。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public boolean findTarget(TreeNode root, int k) {

    List<Integer> list = new ArrayList<>();

    inorderTraversal(root, list);


    int left = 0, right = list.size() - 1;
    while (left < right) {
        //两数之和大于目标值，右指针左移
        if (list.get(left) + list.get(right) > k) {
            right--;
        //两数之和小于目标值，左指针右移
        } else if (list.get(left) + list.get(right) < k) {
            left++;
        } else {
            return true;
        }
    }
    return false;

}

void inorderTraversal(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }

    inorderTraversal(root.left, list);
    list.add(root.val);
    inorderTraversal(root.right, list);
}
  • 时间复杂度：O(N)，需要遍历整棵树
  • 空间复杂度：O(N)，需要一个存储整棵树所有结点值的集合