Explanation: 2 such pairs - [5,4], [2,9]

Example 2:

         10
         / \
        9   20

Input: root = [10, 9, 20], k = 40
Output: false

Solution

Method 1 - Using a Hashset and Dfs

This method works for any tree, so it doesn't take care of features offered by BST.

Code

[{"language":"Java","code":"public boolean findTarget(TreeNode root, int k) {\n\treturn dfs(root, k, new HashSet<>());\n}\n\npublic boolean dfs(TreeNode root, int k, Set<Integer> set){\n\tif(root == null) {\n\t\treturn false;\n\t}\n\tif(set.contains(k - root.val)) {\n\t\treturn true;\n\t}\n\tset.add(root.val);\n\treturn dfs(root.left, set, k) || dfs(root.right, set, k);\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> boolean</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> findTarget</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(TreeNode root, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> k) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\treturn</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> dfs</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(root, k, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">new</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> HashSet&#x3C;>());</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">}</span></span>\n<span class=\"line\"></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> boolean</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> dfs</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(TreeNode root, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> k, Set</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">Integer</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">></span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> set){</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F9758

Related Tags