python - 如何在 O(log n) 时间内遍历这棵二叉树？

Question

今天面试，问题是：

给定这棵二叉树，编写一个函数以仅在 O(log n) 时间内到达任何给定索引。

注意：此二叉树中的数字是索引而不是值。考虑值是空的。

该函数接受 2 个参数：根和我们想要的索引。

def reach_To_Index(root, index)

这棵树和他给我的一模一样

           1
        /     \
      2        3
     / \      /  \
   4    5    6    7
 /  \                
8    9

我的回答是：如果它是二叉搜索树，我可以这样做，但他的回答是，it is not a Binary Search Tree但你可以使用模数来得到答案！

我的问题是可能吗？如果是的话，任何人都可以写这个函数吗！！

标签： pythonpython-3.xpython-2.7

Answer 1

def reach_to_index(node, index):
    if index == 1:
        return node

    power = 2**(int(math.floor(math.log(index, 2))) - 1)
    new_index = power + index % power

    if index < 3 * power:
        return reach_to_index(node.left, new_index)
    return reach_to_index(node.right, new_index)

使用索引的二进制表示：

def reach_to_index(node, index):
    for bit in bin(index)[3:]:
        node = node.left if bit == '0' else node.right
    return node