fork(3) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
### 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
https://ideone.com/PH4KOO
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!