fork(1) download
  1. /*
  2.  * To change this template, choose Tools | Templates
  3.  * and open the template in the editor.
  4.  */
  5. package javaprojects;
  6.  
  7. import java.util.HashSet;
  8. import java.util.Set;
  9.  
  10. /**
  11.  *
  12.  */
  13. public class LCA {
  14.  
  15. private class Node {
  16.  
  17. int data;
  18. Node[] children = new Node[0];
  19. Node parent;
  20.  
  21. public Node() {
  22. }
  23.  
  24. public Node(int v) {
  25. data = v;
  26. }
  27.  
  28. @Override
  29. public boolean equals(Object other) {
  30. if (this.data == ((Node) other).data) {
  31. return true;
  32. }
  33. return false;
  34. }
  35. }
  36. private Node root;
  37.  
  38. public LCA() {
  39. root = new Node(3);
  40.  
  41. root.children = new Node[4];
  42. root.children[0] = new Node(15);
  43. root.children[0].parent = root;
  44. root.children[1] = new Node(40);
  45. root.children[1].parent = root;
  46. root.children[2] = new Node(100);
  47. root.children[2].parent = root;
  48. root.children[3] = new Node(10);
  49. root.children[3].parent = root;
  50.  
  51. root.children[0].children = new Node[3];
  52. root.children[0].children[0] = new Node(22);
  53. root.children[0].children[0].parent = root.children[0];
  54. root.children[0].children[1] = new Node(11);
  55. root.children[0].children[1].parent = root.children[0];
  56. root.children[0].children[2] = new Node(99);
  57. root.children[0].children[2].parent = root.children[0];
  58.  
  59. root.children[2].children = new Node[2];
  60. root.children[2].children[0] = new Node(120);
  61. root.children[2].children[0].parent = root.children[2];
  62. root.children[2].children[1] = new Node(33);
  63. root.children[2].children[1].parent = root.children[2];
  64.  
  65. root.children[3].children = new Node[4];
  66. root.children[3].children[0] = new Node(51);
  67. root.children[3].children[0].parent = root.children[3];
  68. root.children[3].children[1] = new Node(52);
  69. root.children[3].children[1].parent = root.children[3];
  70. root.children[3].children[2] = new Node(53);
  71. root.children[3].children[2].parent = root.children[3];
  72. root.children[3].children[3] = new Node(54);
  73. root.children[3].children[3].parent = root.children[3];
  74.  
  75. root.children[3].children[0].children = new Node[2];
  76. root.children[3].children[0].children[0] = new Node(25);
  77. root.children[3].children[0].children[0].parent = root.children[3].children[0];
  78. root.children[3].children[0].children[1] = new Node(26);
  79. root.children[3].children[0].children[1].parent = root.children[3].children[0];
  80.  
  81. root.children[3].children[3].children = new Node[1];
  82. root.children[3].children[3].children[0] = new Node(27);
  83. root.children[3].children[3].children[0].parent = root.children[3].children[3];
  84. }
  85.  
  86. private Node findNode(Node root, int value) {
  87. if (root == null) {
  88. return null;
  89. }
  90. if (root.data == value) {
  91. return root;
  92. }
  93. for (int i = 0; i < root.children.length; i++) {
  94. Node found = findNode(root.children[i], value);
  95. if (found != null) {
  96. return found;
  97. }
  98. }
  99. return null;
  100. }
  101.  
  102. public void LCA(int node1, int node2) {
  103. Node n1 = findNode(root, node1);
  104. Node n2 = findNode(root, node2);
  105. Set<Node> ancestors = new HashSet<Node>();
  106. while (n1 != null) {
  107. ancestors.add(n1);
  108. n1 = n1.parent;
  109. }
  110. while (n2 != null) {
  111. if (ancestors.contains(n2)) {
  112. System.out.println("Found common ancestor between " + node1 + " and " + node2 + ": node " + n2.data);
  113. return;
  114. }
  115. n2 = n2.parent;
  116. }
  117. }
  118.  
  119. public static void main(String[] args) {
  120. LCA tree = new LCA();
  121. tree.LCA(33, 27);
  122. }
  123. }
  124.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
Main.java:13: class LCA is public, should be declared in a file named LCA.java
public class LCA {
       ^
1 error
stdout

Standard output is empty