Каков путь к корневому узлу в дереве? - PullRequest
Новая
       34

Каков путь к корневому узлу в дереве?

0 голосов
/ 18 июня 2019

Предположим, у нас есть дерево.Особенность этого дерева в том, что оно правильно пронумеровано, но уникальным образом.С корнем дерева связан номер 1, за которым следуют 2 потомка, которые имеют номера 2 и 3 соответственно.Тогда у 2 есть 3 ребенка, а именно 4, 5, 6. У номера 3 также есть 3 ребенка, а именно 7, 8, 9. На следующем уровне, содержащем 4, 5, 6, 7, 8, 9, у каждого есть 2 ребенка.Таким образом, в основном количество детей продолжает меняться в соответствии с паритетом каждого уровня.Если уровень нечетный, то все числа будут иметь 2 детей, в противном случае 3 детей.Вам дадут число n <= 10 ^ 18, и вы должны напечатать весь его путь от корня до самого числа. </p>

Пример тестовых случаев:

Предположим, что n = 2, поэтому путьбудет 1, 2

Предположим, n = 6, поэтому путь будет 1, 2, 6

Предположим, что n = 16, поэтому путь будет 1, 3, 7, 16

1 Ответ

0 голосов
/ 18 июня 2019

вот мое решение:

сначала вам нужно найти уровень n и значение (min, max) этого уровня

ex: n = 2 => level = 2, min, max = (2, 3)

или если n = 5 => level = 3, min, max = (4, 9) 

while max < x:
    min = max + 1
    if level % 2 == 1: # odd
    n *= 2
    max += n
    else: # even
    n *= 3
    max += n
    level += 1

, то мы разделяем всечисла в этих уровнях в пары по 2 или 3 зависят от уровня, в котором мы находимся (пара = 3 для нечетных уровней и пара = 2 для четных) и находят индекс пары, которая имеет n 

        pos = ceil( (x - min + 1) / pair )

с помощью этих 2 формул мы можем написать функцию, которая возвращает массив (min, max, level, pair)

, тогда мы можем найти родителя n, используя: 

    a = f(n)
    b = f(a[0] - 1)
    parent = b[0] + a[3] - 1

здесь, если n= 16 тогда родитель = 7

все, что вам нужно сделать, это продолжать использовать parent, чтобы найти другого родителя n, пока не достигнете 1

...