Administrator
Published on 2025-02-09 / 39 Visits
2
2

二叉树

若我们想求indexij的最近共同祖先:

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

则先对比hihj 大小;后对小者(n)通过k = (n - 1) / 2 的方式反复求父子节点(k),直到hk == hn


Comment