若我们想求index
为i
,j
的最近共同祖先:
i的深度(hi
)为:floor(log2(i + 1))
。
j的深度(hj
)为:floor(log2(j + 1))
。
若hi == hj
则共同祖先的深度为:hi - (2 * abs(((i - 1) / 2) - ((j - 1) / 2)))
。
若hi != hj
则先对比hi
与hj
大小;后对小者(n
)通过k = (n - 1) / 2
的方式反复求父子节点(k
),直到hk == hn
。