两数之和 IV – 输入 BST

全栈程序员站长

发布于 2022-08-25 08:57:50

2050

发布于 2022-08-25 08:57:50

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

两数之和 IV – 输入 BST

题目

两数之和 IV – 输入 BST（力扣：653）

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

分析

使用一个辅助HashSet存储已经遍历过的值，在之后遍历过程中，如果和-当前节点值=HashSet中的任意值，则代表已找到。

代码实现

    /**
     * 653. 两数之和 IV - 输入 BST
     * @param root
     * @param k
     * @return
     */
    public boolean findTarget(TreeNode root, int k) {
        if (root == null){
            return false;
        }
        HashSet<Integer> hashSet = new HashSet<>();
        return findTargetDfs(root, k, hashSet);
    }

    private boolean findTargetDfs(TreeNode root, int k, HashSet<Integer> hashSet){
        if (root == null){
            return false;
        }
        if (hashSet.contains(k - root.val)){
            return true;
        }
        hashSet.add(root.val);
        return findTargetDfs(root.left, k, hashSet) || findTargetDfs(root.right, k, hashSet);
    }

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/141879.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年5月9，如有侵权请联系 cloudcommunity@tencent.com 删除

java