206小R的二叉树探险

题目描述

在一个神奇的二叉树中，结构非常独特：每层的节点值赋值方向是交替的，第一层从左到右，第二层从右到左，以此类推，且该二叉树有无穷多层。
小 R 对这个二叉树充满了好奇，她想知道，在二叉树中两个节点之间 x, y 的路径长度是多少。

题解

不妨直接考虑一颗二叉树全部从左到右编号的情况，这样我们可以获取 x 和 y 在这颗树中的编号，它们之间的相对距离不变

• 奇数层（1、3、5、…）从左到右编号。因此位于奇数层的节点的编号不变
• 偶数层（2、4、6、…）从右到左编号。因此，对于偶数层，需要进行编号的对称转换。
  第k层一共有2^(k-1)个节点，编号从2^(k-1)到2^k-1，并且观察左右对称的节点的编号总和不变，为2^(k-1) + 2^k - 1。因此，对于偶数层的节点n，其对称编号为2^(k-1) + 2^k - 1 - n。

找到节点 x 和 y 到根节点的路径，并记录每个节点在路径中的深度，遍历两个路径，找到最近的公共祖先节点，计算路径长度。

def get_path(n):
    d1 = {}
    k = n.bit_length()
    if k % 2 == 0:
        n = 2 ** k + 2 ** (k - 1) - 1 - n
    for i in range(k):
        d1[n] = i
        n //= 2
    return d1
def solution(x: int, y: int) -> int:
    d1 = get_path(x)
    d2 = get_path(y)
    res = min(d1[k] + d2[k] for k in d1.keys() & d2.keys())
    return res

if __name__ == '__main__':
    print(solution(11, 4) == 5)
    print(solution(2, 5) == 3)
    print(solution(7, 7) == 0)