java - Java 中的 LCA 算法(使用非二叉树)

Question

我使用数组编写了一个非常简单的树类。此类需要表示链接在一起的数据，但它们可以有不同数量的连接(即一条路径可能只有 3 个节点，而另一条路径可能有 10 个)。也就是说，我需要找出一种可能的解决方案来使用具有多个叶索引的此类来执行 LCA。这是我到目前为止编写的代码:

public class ArrayTree {

/**
 * Tree structure
 */
private int[] t;

/**
 * The size of this database
 */
private int N;

/**
 * Creates an array tree with the given size
 * 
 * @param n
 *            the size of the array tree
 */
public ArrayTree(int n) {
    N = n;
    t = new int[N];
}

/**
 * add a new node
 */
public void addNode(int id, int parent) {
    validate(parent);
    t[id] = parent;
}


/**
 * Given an id this method will return an iterable object 
 * orderd from root to leaf
 */
public Iterable<Integer> getEntries(int id) {
    validate(id);
    List<Integer> entries = new ArrayList<Integer>();
    while (id > 1) {
        entries.add(id);
        id = t[id];
        if (id == 0) {
            return null;
        }
    }
    // Reorder entries from root to leaf
    Collections.reverse(entries);
    return entries;
}

/**
 * Private method for validating indexes
 * 
 * @param index
 *            the index
 * @throws IndexOutOfBoundsException
 *             if index > N or index < 0
 */
private void validate(int index) {
    if (index >= N) {
        String error = String.format("Index: %d - Size: %d", index, N);
        throw new IndexOutOfBoundsException(error);
    } else if (index < 0) {
        String error = "negative index";
        throw new IndexOutOfBoundsException(error);
    }
}

}

提前致谢，干杯，

乔瓦尼

Answer 1

多节点的基本 LCA 算法是这样做的:

• 获取每个节点的深度

• 对于每个深度大于最小深度的节点，过渡到父节点，直到所有节点都处于最小深度

• 虽然并非所有节点都相同，但将每个节点转换为其父节点

• 当所有的节点都汇聚到一个节点上，这就是LCA

我真的不能为此提供代码，因为从您的代码中看不出您是如何识别根的，而根是查找节点深度所必需的。