4

我使用数组编写了一个非常简单的树类。此类需要表示链接在一起的数据，但它们可以具有不同数量的连接（即，一条路径可能只有 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);
    }
}

}

在此先感谢，干杯，

乔瓦尼

4

2 回答 2

2

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

  • 获取每个节点的深度

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

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

  • 当所有节点收敛到一个节点时，这就是 LCA

我无法为此提供代码，因为从您的代码中看不出您如何识别根，这对于查找节点的深度是必要的。

于 2015-11-17T13:41:04.213 回答
0

您想找到两个叶节点的 LCA，称它们为node1和node2。

  • 调用getEntries()节点1
  • 调用getEntries()节点2
  • 现在遍历两个列表，直到两个列表上的节点相同
  • 列表中下一个节点不同的第一个节点是 LCA。

这将适用于非二叉树。

于 2015-11-17T14:51:37.100 回答