Interview Question
JD give us very good logic for this problem on chatterous. We will covert BST to Circular Doubly LinkedList in-place.
Then normal two pointer logic
here is the logic for converting BST To DLL
private static TreeNode<Integer> bstToList(TreeNode<Integer> root) {
// TODO Auto-generated method stub
if (root == null)
return null;
TreeNode<Integer> first = bstToList(root.left);
TreeNode<Integer> second = bstToList(root.right);
// Merge first with root and then root with second
root.left = root;
root.right = root;
TreeNode<Integer> aList = append(first, root);
aList = append(aList, second);
return aList;
}
private static TreeNode<Integer> append(TreeNode<Integer> first,
TreeNode<Integer> second) {
// TODO Auto-generated method stub
TreeNode<Integer> l = null;
TreeNode<Integer> r = null;
if (first == null) {
if (second.left == null)
second.left = second;
if (second.right == null)
second.right = second;
return second;
}
if (second == null) {
if (first.left == null)
first.left = first;
if (first.right == null)
first.right = first;
return first;
}
l = first.left;
r = second.left;
l.right = second;
second.left = l;
first.left = r;
r.right = first;
return first;
}
Full code is here ideone com/5mGIM for BST to DLL
Based on following link cslibrary stanford edu/109/TreeListRecursion html
Do a preorder and keep adding nodes and difference = sum - node.val in hashtable. as key, value. Before adding to hash check if the difference exits in the hash table .
I do understand that this not O(1) space complexity.
1) keep two "pointers", one PL at the leftmost and one PR at the rightmost.
- Anonymous July 24, 20102) Add the values of two nodes pointed, say SUM
3) if SUM = k, you ask for a cup of coffee nicely.
4) if SUM > k, you shift your PR to it's predecessor
5) if SUM < k, you shift your PL to it's successor
6) go back to 2) while PR != PL
7) No such two damn nodes.