fork(1) download
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Ideone {
  6.  
  7. static class Node {
  8. List<Node> children = new ArrayList<Node>();
  9. Integer id;
  10. Node(Integer id) {
  11. this.id = id;
  12. }
  13. public String toString() {
  14. return id.toString();
  15. }
  16. }
  17.  
  18. public static void main (String[] args) throws java.lang.Exception {
  19.  
  20. //test data
  21. Node root = new Node(0);
  22. Node n1 = new Node(1);
  23. Node n2 = new Node(2);
  24. Node n3 = new Node(3);
  25. Node n1a = new Node(11);
  26. Node n1b = new Node(12);
  27. Node n3a = new Node(31);
  28. Node n3b = new Node(32);
  29. Node n3c = new Node(33);
  30.  
  31. //connections
  32. root.children.add(n1);
  33. root.children.add(n2);
  34. root.children.add(n3);
  35. n1.children.add(n1a);
  36. n1.children.add(n1b);
  37. n3.children.add(n3a);
  38. n3.children.add(n3b);
  39. n3.children.add(n3c);
  40.  
  41. //tests
  42. System.out.println("### Test 1 ###");
  43. Node r = findClosestCommonAncestor(root, n1b, n3a);
  44. System.out.println("Expected: " + root);
  45. System.out.println("Result: " + r);
  46. System.out.println("Passed --> " + (r == root));
  47.  
  48. System.out.println("### Test 2 ###");
  49. r = findClosestCommonAncestor(root, n3, n3b);
  50. System.out.println("Expected: " + n3);
  51. System.out.println("Result: " + r);
  52. System.out.println("Passed --> " + (r == n3));
  53.  
  54. System.out.println("### Test 3 ###");
  55. r = findClosestCommonAncestor(root, n3a, n3c);
  56. System.out.println("Expected: " + n3);
  57. System.out.println("Result: " + r);
  58. System.out.println("Passed --> " + (r == n3));
  59.  
  60. System.out.println("### Test 4 ###");
  61. r = findClosestCommonAncestor(root, n2, n1a);
  62. System.out.println("Expected: " + root);
  63. System.out.println("Result: " + r);
  64. System.out.println("Passed --> " + (r == root));
  65. }
  66.  
  67. static Node findClosestCommonAncestor(Node root, Node p, Node q) {
  68.  
  69. if (root == null) {
  70. return null;
  71. }
  72.  
  73. if(root == p || root == q) {
  74.  
  75. return root;
  76.  
  77. } else {
  78.  
  79. Node aux = null;
  80.  
  81. //if two children contains p and q, root is the ancestor
  82. for (Node current : root.children) {
  83.  
  84. Node child = findClosestCommonAncestor(current, p, q);
  85. if (child != null) {
  86. if (aux == null) {
  87. aux = child;
  88. } else {
  89. return root;
  90. }
  91. }
  92.  
  93. }
  94. if (aux != null) return aux;
  95.  
  96. }
  97.  
  98. return null;
  99. }
  100.  
  101. }
Success #stdin #stdout 0.07s 380224KB
stdin
Standard input is empty
stdout
### Test 1 ###
Expected: 0
Result: 0
Passed --> true
### Test 2 ###
Expected: 3
Result: 3
Passed --> true
### Test 3 ###
Expected: 3
Result: 3
Passed --> true
### Test 4 ###
Expected: 0
Result: 0
Passed --> true