您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

leetcode 653. 两数之和 IV - 输入 BST

leetcode 653. 两数之和 IV - 输入 BST
给定一个二叉搜索树 root 和一个目标结果 k,如果 BST 中存在两个元素且它们的和等于给定的目标结果,则返回 true。

示例 1:
在这里插入图片描述

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true
示例 2:
在这里插入图片描述

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

提示:

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

解答:Java
方法一:深度优先搜索 + 哈希表
思路和算法:
我们可以使用深度优先搜索的方式遍历整棵树,用哈希表记录遍历过的节点的值。
对于一个值为 xx 的节点,我们检查哈希表中是否存在 k - xk−x 即可。如果存在对应的元素,那么我们就可以在该树上找到两个节点的和为 kk;否则,我们将 xx 放入到哈希表中。
如果遍历完整棵树都不存在对应的元素,那么该树上不存在两个和为 kk 的节点。
方法二:广度优先搜索 + 哈希表
思路和算法:
我们可以使用广度优先搜索的方式遍历整棵树,用哈希表记录遍历过的节点的值。
具体地,我们首先创建一个哈希表和一个队列,将根节点加入队列中,然后执行以下步骤:
从队列中取出队头,假设其值为 xx;
检查哈希表中是否存在 k - xk−x,如果存在,返回 \text{True}True;
否则,将该节点的左右的非空子节点加入队尾;
重复以上步骤,直到队列为空;
如果队列为空,说明树上不存在两个和为 kk 的节点,返回 \text{False}False。

/**
 * 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 Solution {
    Set<Integer> set = new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
        return helper(k,root);
    }
    public boolean helper(int k,TreeNode node){
        int target = k-node.val;
        if (set.contains(target)){
            return true;
        }
        set.add(node.val);
        boolean ans= false;
        if(node.left!=null){
            ans = helper(k,node.left);
        }
        if(node.right!=null&&!ans){
            ans= helper(k,node.right);
        }
        return ans;
    }
}

输入
[5,3,6,2,4,null,7]
9
[5,3,6,2,4,null,7]
28
输出
true
false
预期结果
true
false


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进