653. 两数之和 IV - 输入 BST
653. Two Sum IV - Input is a BST
题目描述
给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
LeetCode653. Two Sum IV - Input is a BST简单
案例 1:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
输出: True
案例 2:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
输出: False
Java 实现
TreeNode Class
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
import java.util.ArrayList;
import java.util.List;
class Solution {
public boolean findTarget(TreeNode root, int k) {
if (root == null) {
return false;
}
return BST(root, k, new ArrayList<>());
}
public boolean BST(TreeNode root, int k, List<Integer> list) {
if (root == null) {
return false;
}
if (list.contains(k - root.val)) {
return true;
}
list.add(root.val);
return BST(root.left, k, list) || BST(root.right, k, list);
}
}
相似题目
- 1. 两数之和 Two Sum
- 167. 两数之和 II - 输入有序数组 Two Sum II - Input array is sorted
- 170. 两数之和 III - 数据结构设计 Two Sum III - Data structure design
参考资料