fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Ideone {
  6.  
  7. 	static class Node {
  8. 		Node parent;
  9. 		Integer id;
  10. 		Node(Integer id, Node parent) {
  11. 			this.id = id;
  12. 			this.parent = parent;
  13. 		}
  14. 		public String toString() {
  15. 			return id.toString();
  16. 		}
  17. 	}
  18.  
  19. 	public static void main (String[] args) throws java.lang.Exception {
  20.  
  21. 		//test data
  22. 		Node root = new Node(0, null);
  23. 		Node n1 = new Node(1, root);
  24. 		Node n2 = new Node(2, root);
  25. 		Node n3 = new Node(3, root);
  26. 		Node n1a = new Node(11, n1);
  27. 		Node n1b = new Node(12, n1);
  28. 		Node n3a = new Node(31, n3);
  29. 		Node n3b = new Node(32, n3);
  30. 		Node n3c = new Node(33, n3);
  31.  
  32. 		//tests
  33. 		System.out.println("### Test 1 ###");
  34. 		Node r = findClosestCommonAncestor(n1b, n3a);
  35. 		System.out.println("Expected: " + root);
  36. 		System.out.println("Result: " + r);
  37. 		System.out.println("Passed --> " + (r == root));
  38.  
  39. 		System.out.println("### Test 2 ###");
  40. 		r = findClosestCommonAncestor(n3, n3b);
  41. 		System.out.println("Expected: " + n3);
  42. 		System.out.println("Result: " + r);
  43. 		System.out.println("Passed --> " + (r == n3));
  44.  
  45. 		System.out.println("### Test 3 ###");
  46. 		r = findClosestCommonAncestor(n3a, n3c);
  47. 		System.out.println("Expected: " + n3);
  48. 		System.out.println("Result: " + r);
  49. 		System.out.println("Passed --> " + (r == n3));
  50.  
  51. 		System.out.println("### Test 4 ###");
  52. 		r = findClosestCommonAncestor(n2, n1a);
  53. 		System.out.println("Expected: " + root);
  54. 		System.out.println("Result: " + r);
  55. 		System.out.println("Passed --> " + (r == root));
  56.  
  57. 	}
  58.  
  59. 	static Node findClosestCommonAncestor(Node p, Node q) {
  60. 		if (p == null || q == null) return null;
  61.  
  62. 		//guarda os pais do nó P, incluindo o próprio
  63.         Set<Node> parentsOfP = new HashSet<Node>();
  64.         while (p != null) {
  65.         	parentsOfP.add(p);
  66.         	p = p.parent;
  67.         }
  68.  
  69. 		//procura o primeiro pai de Q que está entre os pais de P
  70.         while (q != null) {
  71.         	if (parentsOfP.contains(q)) {
  72.         		return q;
  73.         	}
  74.         	q = q.parent;
  75.         }
  76.         return null;// not in the same tree
  77.    	}
  78.  
  79.  
  80. }
Success #stdin #stdout 0.12s 320576KB
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/y89WEH
language:
Java (HotSpot 12)
created:
7 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!