Реализация Euler Tour в Python

Question

Я пытаюсь реализовать следующий Euler Tour на Python.

Однако я застрял на хранении высших значений. Моя реализация кода:

       def rmq(root, level, prev=None):
    if not root:
        return True
    euler.append(root.data)
    levels.append(level)  
    ret = rmq(root.left, level+1, (root.data, level))
    ret = rmq(root.right, level+1, (root.data, level))  
    if not (root.left or root.right):
        euler.append(prev[0])
        levels.append(prev[1])
        return True
    if ret:
        euler.append(root.data)
        levels.append(level)


levels = []
euler = []
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.right.left = Node(8)
root.left.right.right = Node(9)

rmq(root, 0)
print(euler)
print(levels)

И вывод, который я получаю из приведенного выше кода, для списков Эйлера и:

       [1, 2, 4, 2, 5, 8, 5, 9, 5, 5, 3, 6, 3, 7, 3, 3]

[0, 1, 2, 1, 2, 3, 2, 3, 2, 2, 1, 2, 1, 2, 1, 1] 

Конечная цель - реализовать это, но более простым способом.

Пожалуйста, помогите мне достичь конечной цели.

Answer 1

Нет необходимости передавать текущий элемент на следующий уровень рекурсии. Проще обрабатывать сохранение значений каждого элемента на их собственном уровне рекурсии, как это (я переписал хранилище дерева, чтобы избежать явного вызова левого и правого элементов):

nodeChildren = {
    1: [2, 3],
    2: [4, 5],
    5: [8, 9],
    3: [6, 7]
}

elements = []
levels = []


def traverseNode(node, level=0):
    elements.append(node)
    levels.append(level)
    if node in nodeChildren:
        for child in nodeChildren[node]:
            traverseNode(child, level+1)
            elements.append(node)
            levels.append(level)


traverseNode(1)

print(f"node elements: {elements}")
# output: node elements: [1, 2, 4, 2, 5, 8, 5, 9, 5, 2, 1, 3, 6, 3, 7, 3, 1]

print(f"levels: {levels}")
# output: levels: [0, 1, 2, 1, 2, 3, 2, 3, 2, 1, 0, 1, 2, 1, 2, 1, 0]

Пояснение:

• объект nodeChildren - это карта: для каждого номера узла, у которого есть дочерние элементы, дается список дочерних элементов. Это будет работать для любого дерева (обратите внимание, я не предвидел механизма обнаружения циклов - в этом случае вы получите переполнение стека:))
• traversnode добавит его номер и уровень в соответствующие списки
• он проверит, есть ли у текущего узла дочерние элементы. Если это так, он будет рекурсивно проходить по этим дочерним элементам и повторно добавлять себя в списки чисел и уровней.