我有一个BST的后序遍历,如[3,6,5,1,12,16,15,10,20,7],我想找到它的预序遍历,如[7,1,5,3,6,20,10,15,12,16]。是否可以在不构造树的情况下找到递归解决方案?[已编辑]
这是一个不构建树的递归函数。它从头到尾遍历后序列表,因为这几乎代表了所需的顺序,除了以相反的顺序访问子项:
def preordered(postorder):
def recur(granny, parent):
if not postorder or postorder[-1] < min(granny, parent):
return []
value = postorder.pop()
right = recur(parent, value)
left = recur(parent, value)
return [value] + left + right
low = min(postorder)
postorder = postorder[:]
return recur(low, low)
result = preordered([3,6,5,1,12,16,15,10,20,7])