描述
Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
1 2 3 4 5 6 7 8 9 10
| Input: 5 / \ 3 6 / \ \ 2 4 7
Target = 9
Output: True
|
Example 2:
1 2 3 4 5 6 7 8 9 10
| Input: 5 / \ 3 6 / \ \ 2 4 7
Target = 28
Output: False
|
分析
可以使用哈希集合存树节点的值,遍历二叉树可以使用深度优先算法。
解决方案1(Java)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
|
class Solution { public boolean findTarget(TreeNode root, int k) { Set<Integer> set = new HashSet(); return DFS(root, k, set); } private boolean DFS(TreeNode root, int k, Set<Integer> set) { if (root == null) { return false; } if (set.contains(k-root.val)) { return true; } set.add(root.val); return DFS(root.left, k, set) || DFS(root.right, k, set); } }
|
相关问题