import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone {
static class Node {
Node parent;
this.id = id;
this.parent = parent;
}
return id.toString();
}
}
//test data
Node root = new Node(0, null);
Node n1 = new Node(1, root);
Node n2 = new Node(2, root);
Node n3 = new Node(3, root);
Node n1a = new Node(11, n1);
Node n1b = new Node(12, n1);
Node n3a = new Node(31, n3);
Node n3b = new Node(32, n3);
Node n3c = new Node(33, n3);
//tests
System.
out.
println("### Test 1 ###"); Node r = findClosestCommonAncestor(n1b, n3a);
System.
out.
println("Expected: " + root
); System.
out.
println("Result: " + r
); System.
out.
println("Passed --> " + (r
== root
));
System.
out.
println("### Test 2 ###"); r = findClosestCommonAncestor(n3, n3b);
System.
out.
println("Expected: " + n3
); System.
out.
println("Result: " + r
); System.
out.
println("Passed --> " + (r
== n3
));
System.
out.
println("### Test 3 ###"); r = findClosestCommonAncestor(n3a, n3c);
System.
out.
println("Expected: " + n3
); System.
out.
println("Result: " + r
); System.
out.
println("Passed --> " + (r
== n3
));
System.
out.
println("### Test 4 ###"); r = findClosestCommonAncestor(n2, n1a);
System.
out.
println("Expected: " + root
); System.
out.
println("Result: " + r
); System.
out.
println("Passed --> " + (r
== root
));
}
static Node findClosestCommonAncestor(Node p, Node q) {
if (p == null || q == null) return null;
//guarda os pais do nó P, incluindo o próprio
Set<Node> parentsOfP = new HashSet<Node>();
while (p != null) {
parentsOfP.add(p);
p = p.parent;
}
//procura o primeiro pai de Q que está entre os pais de P
while (q != null) {
if (parentsOfP.contains(q)) {
return q;
}
q = q.parent;
}
return null;// not in the same tree
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBJZGVvbmUgewoJCglzdGF0aWMgY2xhc3MgTm9kZSB7CgkJTm9kZSBwYXJlbnQ7CgkJSW50ZWdlciBpZDsKCQlOb2RlKEludGVnZXIgaWQsIE5vZGUgcGFyZW50KSB7CgkJCXRoaXMuaWQgPSBpZDsKCQkJdGhpcy5wYXJlbnQgPSBwYXJlbnQ7CgkJfQoJCXB1YmxpYyBTdHJpbmcgdG9TdHJpbmcoKSB7CgkJCXJldHVybiBpZC50b1N0cmluZygpOwoJCX0KCX0KCQoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBqYXZhLmxhbmcuRXhjZXB0aW9uIHsKCQkKCQkvL3Rlc3QgZGF0YQoJCU5vZGUgcm9vdCA9IG5ldyBOb2RlKDAsIG51bGwpOwoJCU5vZGUgbjEgPSBuZXcgTm9kZSgxLCByb290KTsKCQlOb2RlIG4yID0gbmV3IE5vZGUoMiwgcm9vdCk7CgkJTm9kZSBuMyA9IG5ldyBOb2RlKDMsIHJvb3QpOwoJCU5vZGUgbjFhID0gbmV3IE5vZGUoMTEsIG4xKTsKCQlOb2RlIG4xYiA9IG5ldyBOb2RlKDEyLCBuMSk7CgkJTm9kZSBuM2EgPSBuZXcgTm9kZSgzMSwgbjMpOwoJCU5vZGUgbjNiID0gbmV3IE5vZGUoMzIsIG4zKTsKCQlOb2RlIG4zYyA9IG5ldyBOb2RlKDMzLCBuMyk7CgkJCgkJLy90ZXN0cwoJCVN5c3RlbS5vdXQucHJpbnRsbigiIyMjIFRlc3QgMSAjIyMiKTsKCQlOb2RlIHIgPSBmaW5kQ2xvc2VzdENvbW1vbkFuY2VzdG9yKG4xYiwgbjNhKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIkV4cGVjdGVkOiAiICsgcm9vdCk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJSZXN1bHQ6ICIgKyByKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIlBhc3NlZCAtLT4gIiArIChyID09IHJvb3QpKTsKCQkKCQlTeXN0ZW0ub3V0LnByaW50bG4oIiMjIyBUZXN0IDIgIyMjIik7CgkJciA9IGZpbmRDbG9zZXN0Q29tbW9uQW5jZXN0b3IobjMsIG4zYik7CgkJU3lzdGVtLm91dC5wcmludGxuKCJFeHBlY3RlZDogIiArIG4zKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIlJlc3VsdDogIiArIHIpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiUGFzc2VkIC0tPiAiICsgKHIgPT0gbjMpKTsKCQkKCQlTeXN0ZW0ub3V0LnByaW50bG4oIiMjIyBUZXN0IDMgIyMjIik7CgkJciA9IGZpbmRDbG9zZXN0Q29tbW9uQW5jZXN0b3IobjNhLCBuM2MpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiRXhwZWN0ZWQ6ICIgKyBuMyk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJSZXN1bHQ6ICIgKyByKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIlBhc3NlZCAtLT4gIiArIChyID09IG4zKSk7CgkJCgkJU3lzdGVtLm91dC5wcmludGxuKCIjIyMgVGVzdCA0ICMjIyIpOwoJCXIgPSBmaW5kQ2xvc2VzdENvbW1vbkFuY2VzdG9yKG4yLCBuMWEpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiRXhwZWN0ZWQ6ICIgKyByb290KTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIlJlc3VsdDogIiArIHIpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiUGFzc2VkIC0tPiAiICsgKHIgPT0gcm9vdCkpOwoJCQoJfQoJCglzdGF0aWMgTm9kZSBmaW5kQ2xvc2VzdENvbW1vbkFuY2VzdG9yKE5vZGUgcCwgTm9kZSBxKSB7CgkJaWYgKHAgPT0gbnVsbCB8fCBxID09IG51bGwpIHJldHVybiBudWxsOwoJCQoJCS8vZ3VhcmRhIG9zIHBhaXMgZG8gbsOzIFAsIGluY2x1aW5kbyBvIHByw7NwcmlvCiAgICAgICAgU2V0PE5vZGU+IHBhcmVudHNPZlAgPSBuZXcgSGFzaFNldDxOb2RlPigpOwogICAgICAgIHdoaWxlIChwICE9IG51bGwpIHsKICAgICAgICAJcGFyZW50c09mUC5hZGQocCk7CiAgICAgICAgCXAgPSBwLnBhcmVudDsKICAgICAgICB9CiAgICAgICAgCgkJLy9wcm9jdXJhIG8gcHJpbWVpcm8gcGFpIGRlIFEgcXVlIGVzdMOhIGVudHJlIG9zIHBhaXMgZGUgUAogICAgICAgIHdoaWxlIChxICE9IG51bGwpIHsKICAgICAgICAJaWYgKHBhcmVudHNPZlAuY29udGFpbnMocSkpIHsKICAgICAgICAJCXJldHVybiBxOwogICAgICAgIAl9CiAgICAgICAgCXEgPSBxLnBhcmVudDsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIG51bGw7Ly8gbm90IGluIHRoZSBzYW1lIHRyZWUKICAgCX0KCgp9