lekuocom
BAN USER. 5
. / \
. 3 7
./\ / \
2 4 6 8
swap 7 and 3
. 5
. / \
. 3 7
./\ / \
2 4 6 8
swap 3 & 7;
. 3
. / \
. 5 4
./\
2 7
./ \
6 8
swap 5 & 7;
. 7
. / \
. 6 5
. / \
. 3 8
./ \
2 4
public static class Sol_1 {
//n1 && n2 should not be null
public static Node swap(Node r, Node n1, Node n2) {
if (r == null)
return null;
if (r == n1) {
r = n2;
if (childSwap(n1, n2))
return r;
} else if (r == n2) {
r = n1;
if (childSwap(n2, n1))
return r;
}
r.left = swap(r.left, n1, n2);
r.right = swap(r.right, n1, n2);
return r;
}
//return true if swapped with child
private static boolean childSwap(Node r, Node c) {
if (r.left == c) {
Node cl = c.left;
c.left = r;
r.left = cl;
return true;
} else if (r.right == c) {
Node cr = c.right;
c.right = r;
r.right = cr;
return true;
}
return false;
}
}
define class DoubleLinkedList<Item>
1. using DoubleLinkedList instead of ArrayList, which guarantee O(1) delete and Insertion.
2. TreeMap<KeyValue, List<DoubleLinkedListNode<Item>> for each key;
3. HashMap<KeyType, TreeMap<...> mapOfIndexes;
...
Insert / delete / search: O(log(N))
Iterate: O(N)
Union-find and tree traverse have similar space and time requirements.
- lekuocom July 17, 2014Tree traverse by DFS may need recursive call.