python - 在 Python 中实现 Euler Tour

Question

我正在尝试在 Python 中实现以下 Euler Tour。

但是，我坚持存储最高值。我的代码实现是：

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 会将其编号和级别添加到相应的列表中
• 它将检查当前节点是否有任何子节点。如果是这样，它将递归地遍历这些孩子并将自己重新附加到数字和级别列表中。