通关剑指 Offer——剑指 Offer II 056. 二叉搜索树中两个节点之和

1.题目描述

剑指 Offer II 056. 二叉搜索树中两个节点之和

给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。

示例 1：

输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12

示例 2：

输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点

2.解题思路与代码

2.1 解题思路

非常简单的一道题目，首先遍历二叉树，然后将遍历的结果放入一个 HashSet 中，此时我们就得到了这棵二叉树的所有节点值。然后我们遍历这个 HashSet 中的元素，先用目标总和减去遍历到的节点值得到要查找的值 find，然后在这个 HashSet 中查找 find 是否存在，如果存在直接返回 true，表示有两个节点的值总和为目标 k，如果不存在继续便利。

这里需要注意如果当前节点的值与要查找的目标值相同，那么需要跳过这种情况，因为题目要求二叉树中节点的值是唯一的，因此虽然 HashSet 中包含 find，但此时找到的值就是当前节点，不满足题意。当然我们也可以使用 List 来存放二叉树节点的遍历结果。

2.2 代码

class Solution {
    Set<Integer> set = new HashSet<>();

    public boolean findTarget(TreeNode root, int k) {
        process(root);
        for (Integer key : set) {
            int find = k - key;
            if (find == key) {
                continue;
            }
            if (set.contains(find)) {
                return true;
            }
        }
        return false;
    }

    public void process(TreeNode root) {
        if (root == null) {
            return;
        }
        process(root.left);
        set.add(root.val);
        process(root.right);
    }
}

2.3 测试结果

通过测试

3.总结

• 遍历二叉树，并将结果放入 HashSet 中
• 需要跳过查找值和节点值相同的情况