fork(2) 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.  
  68. 	static Node findClosestCommonAncestor(Node node, Node p, Node q) {
  69.  
  70.         Stack<Node> parentStack = new Stack<Node>();
  71.         Stack<Integer> childIndexStack = new Stack<Integer>();
  72.         Stack<Node> firstNodePath = null;
  73.         while (!parentStack.empty() || node != null) {
  74.  
  75.         	if (node != null) {
  76.  
  77.         		if (node == p || node == q) {
  78.  
  79.         			if (firstNodePath != null) {
  80.         				parentStack.add(node);
  81.         				int n = Math.min(parentStack.size(), firstNodePath.size());
  82.         				for (int i = n - 1; i >= 0; i--) {
  83.         					if (parentStack.get(i) == firstNodePath.get(i)) {
  84.         						return parentStack.get(i); 
  85.         					}
  86. 						}
  87.        					return null;
  88.  
  89.         			} else {
  90.         				firstNodePath = new Stack<Node>();
  91.         				firstNodePath.setSize(parentStack.size());
  92.         				Collections.copy(firstNodePath, parentStack);
  93.         				firstNodePath.push(node);
  94.         			}
  95.  
  96.         		}
  97.  
  98.         		if (!node.children.isEmpty()) {
  99.         			parentStack.push(node);
  100.         			childIndexStack.push(0);
  101.         			node = node.children.get(0);
  102.         		} else {
  103.         			node = null;
  104.         		}
  105.  
  106.         	} else {
  107.  
  108.         		node = parentStack.peek();
  109.         		Integer i = childIndexStack.pop() + 1;
  110.         		if (i >= node.children.size()) {
  111.         			node = null;
  112.         			parentStack.pop();
  113.         		} else {
  114.         			node = node.children.get(i);
  115.         			childIndexStack.push(i);
  116.         		}
  117.  
  118. 	        }
  119.  
  120.         }
  121.         return null;
  122.  
  123. 	}
  124.  
  125.  
  126. }
Success #stdin #stdout 0.08s 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/JcNkf6
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!