LeetCode Easy653中两数之和输入为BST的示例分析
发表于:2024-09-22 作者:千家信息网编辑
千家信息网最后更新 2024年09月22日,LeetCode Easy653中两数之和输入为BST的示例分析,针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。Description
千家信息网最后更新 2024年09月22日LeetCode Easy653中两数之和输入为BST的示例分析
LeetCode Easy653中两数之和输入为BST的示例分析,针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。
Description
https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input: root = [5,3,6,2,4,null,7], k = 9Output: true
Example 2:
Input: root = [5,3,6,2,4,null,7], k = 28Output: false
Example 3:
Input: root = [2,1,3], k = 4Output: true
Example 4:
Input: root = [2,1,3], k = 1Output: false
Example 5:
Input: root = [2,1,3], k = 3 Output: true
Constraints:
The number of nodes in the tree is in the range $[1, 10^4]$.
$-10^4 <= Node.val <= 10^4$
root
is guaranteed to be a valid binary search tree.$-10^5 <= k <= 10^5$
Analysis
用两指针方法,一指针前序遍历,另一指针二分查找。
Submission
public class TwoSumIVInputIsABST { public boolean findTarget(TreeNode root, int k) { return traverse(root, root, k); } // 前序遍历 private boolean traverse(TreeNode node, TreeNode root, int k) { if (node == null) return false; // node.val恰好是k的一半时,根据BST特性,没必要找另一个节点 if (2 * node.val != k && findTarget2(root, k - node.val)) return true; return traverse(node.left, root, k) || traverse(node.right, root, k); } // 二分查找 private boolean findTarget2(TreeNode node, int targetValue) { if (node == null) return false; if (node.val == targetValue) return true; return findTarget2(targetValue < node.val ? node.left : node.right, targetValue); }}
Test
import static org.junit.Assert.*;import org.junit.Test;import com.lun.util.BinaryTree;import com.lun.util.BinaryTree.TreeNode;public class TwoSumIVInputIsABSTTest { @Test public void test() { TwoSumIVInputIsABST obj = new TwoSumIVInputIsABST(); TreeNode root1 = BinaryTree.integers2BinaryTree(5, 3, 6, 2, 4, null, 7); assertTrue(obj.findTarget(root1, 9)); assertFalse(obj.findTarget(root1, 28)); TreeNode root2 = BinaryTree.integers2BinaryTree(2, 1, 3); assertTrue(obj.findTarget(root2, 4)); assertFalse(obj.findTarget(root2, 1)); assertTrue(obj.findTarget(root2, 3)); }}
关于LeetCode Easy653中两数之和输入为BST的示例分析问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注行业资讯频道了解更多相关知识。
分析
指针
问题
之和
示例
输入
方法
更多
帮助
解答
易行
必要
简单易行
内容
小伙
小伙伴
特性
知识
篇文章
节点
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
手机企业软件开发平台有哪些
互联网科技自媒体创业项目
辽源节能软件开发定制
小米软件开发介绍
软件开发和网络哪个简单
newworld服务器在哪
昆仑服务器初始管理账号密码
海康蜂鸟服务器管理平台
服务器邮箱架设
299元的服务器
女生学嵌入式软件开发好不好
陕西服务器维修费用
人类死亡率数据库和欧洲统计局
宁国软件开发公司哪家靠谱
专注防护服务器
苏州荣越网络技术有限公司
软件开发云优点
网络安全特色活动主持稿
怎样启动svn服务器
软件开发需要具备数学知识吗
网络安全排查整改情况
数据库转码工具下载
mvn项目怎么连接数据库
英雄联盟是哪个地方的服务器
非商用网络技术问题由谁负责
网络安全基本知识竞赛试题
软件开发游戏公司
单机数据库开发教程
软件开发所需
机器人网络技术发展