Two Sum IV




@vinod23 whats your take on converting the BST to doubly linked list and then find the two sum.

@kool This cannot be done in O(n) time and O(logN) space. What if height of my BST is N?

@vinod32 My first solution has better bounds than the listed ones. https://leetcode.com/submissions/detail/125833106/ It's similar to approach #3, but only uses O(Depth) space which is log2(N) when the tree is balanced. You do not need to put all tree elements in the list. Just traverse the tree itself.


def __findTargetDetail(self, root, k, seen): if root is None: return False complement = k  root.val if complement in seen: return True else: seen.add(root.val) return self.__findTargetDetail(root.left, k, seen) or self.__findTargetDetail(root.right, k, seen) # O(n) time, O(n) space def findTarget(self, root, k): seen = set() return self.__findTargetDetail(root, k, seen)

def __binarySearch(self, root, k): if root is None: return if root.val == k: return root elif root.val > k: return self.__binarySearch(root.left, k) else: return self.__binarySearch(root.right, k) def __findTargetBST(self, node, root, k): if node is None: return False complement = k  node.val comp_node = self.__binarySearch(root, complement) if comp_node is not None and node is not comp_node: return True return self.__findTargetBST(node.left, root, k) or self.__findTargetBST(node.right, root, k) # O(nlogn) time, O(h) space def findTarget(self, root, k): return self.__findTargetBST(root, root, k)

# O(n) time, O(n) space, use BFS def findTarget(self, root, k): if root is None: return False s = set() q = Queue.Queue() q.put(root) while not q.empty(): node = q.get() complement = k  node.val if complement in s: return True else: s.add(node.val) if node.left: q.put(node.left) if node.right: q.put(node.right) return False

/**

Definition for a binary tree node.

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};
/
class Solution {
public:
bool findTarget(TreeNode root, int k) {
if (root == NULL) {
return false;
}
vector<int> v;
inorder(root, v);int low = 0; int high = v.size()  1; while (low < high) { if (v[low] + v[high] == k) { return true; } else if (v[low] + v[high] < k) { low++; } else { high; } } return false;
}
private:
void inorder(TreeNode* root, vector<int>& v) {
if (root != NULL) {
inorder(root>left, v);
v.push_back(root>val);
inorder(root>right, v);
}
}
};



@Enjoy_Code Put ``` Code``` around your code. You can take a look at https://discuss.leetcode.com/topic/22/welcomenewuserspleasereadthisbeforeposting

public boolean findTarget(TreeNode root, int k) { java.util.Map<Integer, Object> m = new java.util.HashMap<>(); flat(root, m); for (java.util.Map.Entry<Integer, Object> e : m.entrySet()) { int complement = k  e.getKey(); if (complement != e.getKey() // avoid like 6  3 = 3 issue; && m.containsKey(complement)) { return true; } } return false; } /** * recursively get values from the tree and put into map. */ public void flat(TreeNode node, java.util.Map<Integer,Object> m) { m.put(node.val, null); if(node.left != null) flat(node.left, m); if(node.right != null) flat(node.right, m); }
}