用Python实现Euler旅游

Question

我试图用Python实现下面的Euler旅游。

​

​

然而，我被困在存储顶级值上。我的代码实现是：

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)

和我从上面的代码中得到的输出，对于lists，是：

[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

不需要将当前元素传递到下一个递归级别。在自己的递归级别上更容易处理每个elemen‘’ts值的存储，就像这样(我确实重写了树的存储，以避免显式调用左元素和右元素)：

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对象是一个映射:对于每个有子节点的节点数，都会给出一个子节点列表。这将适用于任何类型的树(注意，我没有预见到检测循环的机制--在这种情况下，您将得到堆栈溢出:)
• 遍历节点将把它的数量和级别添加到相应的列表中
• 它将检查cuurent节点是否有任何子节点。如果是这样的话，它将递归遍历这些子节点，并将自己重新附加到数字和级别列表中。