20201016

BoscoSuen · BoscoSuen · commit c30c1c860b65 · 2020-10-16T00:41:11.000-07:00
diff --git a/Java/653.two-sum-iv-input-is-a-bst.java b/Java/653.two-sum-iv-input-is-a-bst.java
@@ -0,0 +1,40 @@
+/*
+ * @lc app=leetcode id=653 lang=java
+ *
+ * [653] Two Sum IV - Input is a BST
+ */
+
+// @lc code=start
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode() {}
+ *     TreeNode(int val) { this.val = val; }
+ *     TreeNode(int val, TreeNode left, TreeNode right) {
+ *         this.val = val;
+ *         this.left = left;
+ *         this.right = right;
+ *     }
+ * }
+ */
+class Solution {
+    public boolean findTarget(TreeNode root, int k) {
+        if (root == null) return false;
+        Set<Integer> set = new HashSet<>();
+        return dfs(root, set, k);
+    }
+
+    private boolean dfs(TreeNode root, Set<Integer> set, int k) {
+        if (root == null) return false;
+        if (set.contains(k - root.val)) {
+            return true;
+        }
+        set.add(root.val);
+        return dfs(root.left, set, k) || dfs(root.right, set, k);
+    }
+}
+// @lc code=end
+
