我希望能够以编程方式检查数组，并确定它是否是加权快速联合算法的结果。对于我们这些需要复习的人来说，这里有一个加权快速联合的java实现。
加权快速并集算法的基本思想是，它总是将较小的树与较大的树连接起来，以最小化高度，从而优化任何遍历函数。
例如，一个看起来像8 4 8 8 8 3 8 3 9 7的数组不可能是加权快速并集的结果，因为它包含一个循环9->7->3->8->9
像8 0 9 3 6 6 0 4 8 0这样的数组不能是加权的快速并集，因为树的高度加在一起是4，大于log（N）（其中N是10，初始数组的大小）。
然而，像0 1 2 8 4 1 1 7 8 9这样的数组可能是加权快速并集的结果。
我想写一个这样的Java函数：
public static boolean canBeResultOfWeightedQuickUnion(int[] id){
//returns whether or not the given array of ints could have been the result of a weighted quick union
}
我该如何编写这样的方法，最好使用这里可用的数据结构？
"像***这样的数组不能是加权快速并集，因为树的高度加在一起是4，大于log（N）（其中N是10，初始数组的大小）。"
事实上，在这种情况下，最大高度是ceil（log_2（N）），即4要检查这一点，只需从一开始就合并高度相同的树
这个属性对所有子树都保留，这是一个很好的答案，因为您只需要检查这个属性。
仍然存在的问题是，你如何才能以最高的效率做到这一点。我想你刚刚收到一个数组，正在检查它。所以没有其他信息可用。如果是这种情况，您可以为高度创建一个辅助数组。然后，您必须遍历id数组，找到叶，然后在第二步中递归地从叶到根，更新高度值并与子树中的元素数量进行比较。