小编给大家分享一下LeetCode如何判断两数之和的结果是否等于给定的目标结果,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!
1,问题简述
给定一个二叉搜索树和一个目标结果,如果 BST 中存在两个元素且它们的和等于给定的目标结果,则返回 true。
2,示例
案例 1:
输入:
5
/ /
3 6
/ / /
2 4 7
Target = 9
输出: True
案例 2:
输入:
5
/ /
3 6
/ / /
2 4 7
Target = 28
输出: False
3,题解思路
基于二叉树的中序遍历和双指针的思路进行求解
4,题解程序
import java.util.ArrayList;
import java.util.List;
public class FindTargetTest {
private static List<Integer> list = new ArrayList<>();
public static void main(String[] args) {
TreeNode t1 = new TreeNode(5);
TreeNode t2 = new TreeNode(3);
TreeNode t3 = new TreeNode(6);
TreeNode t4 = new TreeNode(2);
TreeNode t5 = new TreeNode(4);
TreeNode t6 = new TreeNode(7);
t1.left = t2;
t1.right = t3;
t2.left = t4;
t2.right = t5;
t3.right = t6;
int k = 9;
boolean target = findTarget(t1, k);
System.out.println("target = " + target);
}
public static boolean findTarget(TreeNode root, int k) {
if (root == null) {
return false;
}
inOrder(root);
int i = 0;
int j = list.size() - 1;
while (i < j) {
Integer left = list.get(i);
Integer right = list.get(j);
if (left + right == k) {
return true;
} else if (left + right > k) {
j--;
} else {
i++;
}
}
return false;
}
private static void inOrder(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
inOrder(root.left);
}
list.add(root.val);
if (root.right != null) {
inOrder(root.right);
}
}
}
5,题解程序图片版
看完了这篇文章,相信你对“LeetCode如何判断两数之和的结果是否等于给定的目标结果”有了一定的了解,如果想了解更多相关知识,欢迎关注亿速云行业资讯频道,感谢各位的阅读!
原创文章,作者:bd101bd101,如若转载,请注明出处:https://blog.ytso.com/tech/opensource/223579.html