我一直在阅读有关顶级编码器的最低公共祖先算法，但我不明白为什么涉及 RMQ 算法 - 那里列出的解决方案非常复杂，并且具有以下属性：
- 搜索的 O(sqrt(n)) 时间复杂度，O(n) 预计算时间复杂度
- 存储每个节点的父节点的 O(n) 空间复杂度
- 再次为 O(n) 空间复杂度，用于存储每个节点的预计算
我的解决方案：给定 2 个整数值，通过简单的前序遍历找到节点。取其中一个节点并上树并将路径存储到一个集合中。取另一个节点并向上走，并在我向上时检查每个节点：如果该节点在 Set 中，则停止并返回 LCA。全面实施。
- 给定值，找到 2 个节点中的每一个的 O(n) 时间复杂度（因为它是常规树，而不是 BST -
- 将路径存储到集合中的 O(log n) 空间复杂度
- O(log n) 使用第二个节点上树的时间复杂度
那么鉴于这两个选择，Top Coder 上的算法是否更好，如果是，为什么？这是我无法理解的。我认为 O(log n) 比 O(sqrt(n)) 好。
public class LCA {
private class Node {
int data;
Node[] children = new Node[0];
Node parent;
public Node() {
}
public Node(int v) {
data = v;
}
@Override
public boolean equals(Object other) {
if (this.data == ((Node) other).data) {
return true;
}
return false;
}
}
private Node root;
public LCA() {
root = new Node(3);
root.children = new Node[4];
root.children[0] = new Node(15);
root.children[0].parent = root;
root.children[1] = new Node(40);
root.children[1].parent = root;
root.children[2] = new Node(100);
root.children[2].parent = root;
root.children[3] = new Node(10);
root.children[3].parent = root;
root.children[0].children = new Node[3];
root.children[0].children[0] = new Node(22);
root.children[0].children[0].parent = root.children[0];
root.children[0].children[1] = new Node(11);
root.children[0].children[1].parent = root.children[0];
root.children[0].children[2] = new Node(99);
root.children[0].children[2].parent = root.children[0];
root.children[2].children = new Node[2];
root.children[2].children[0] = new Node(120);
root.children[2].children[0].parent = root.children[2];
root.children[2].children[1] = new Node(33);
root.children[2].children[1].parent = root.children[2];
root.children[3].children = new Node[4];
root.children[3].children[0] = new Node(51);
root.children[3].children[0].parent = root.children[3];
root.children[3].children[1] = new Node(52);
root.children[3].children[1].parent = root.children[3];
root.children[3].children[2] = new Node(53);
root.children[3].children[2].parent = root.children[3];
root.children[3].children[3] = new Node(54);
root.children[3].children[3].parent = root.children[3];
root.children[3].children[0].children = new Node[2];
root.children[3].children[0].children[0] = new Node(25);
root.children[3].children[0].children[0].parent = root.children[3].children[0];
root.children[3].children[0].children[1] = new Node(26);
root.children[3].children[0].children[1].parent = root.children[3].children[0];
root.children[3].children[3].children = new Node[1];
root.children[3].children[3].children[0] = new Node(27);
root.children[3].children[3].children[0].parent = root.children[3].children[3];
}
private Node findNode(Node root, int value) {
if (root == null) {
return null;
}
if (root.data == value) {
return root;
}
for (int i = 0; i < root.children.length; i++) {
Node found = findNode(root.children[i], value);
if (found != null) {
return found;
}
}
return null;
}
public void LCA(int node1, int node2) {
Node n1 = findNode(root, node1);
Node n2 = findNode(root, node2);
Set<Node> ancestors = new HashSet<Node>();
while (n1 != null) {
ancestors.add(n1);
n1 = n1.parent;
}
while (n2 != null) {
if (ancestors.contains(n2)) {
System.out.println("Found common ancestor between " + node1 + " and " + node2 + ": node " + n2.data);
return;
}
n2 = n2.parent;
}
}
public static void main(String[] args) {
LCA tree = new LCA();
tree.LCA(33, 27);
}
}