python - 如何从给定的二叉搜索树的后序遍历中找到前序遍历
问题描述
我有一个像 [3,6,5,1,12,16,15,10,20,7] 这样的 BST 的后序遍历,我想找到它的像 [7,1,5, 3,6,20,10,15,12,16]。是否可以在不构建树的情况下找到递归解决方案?[已编辑]
解决方案
这是一个没有构建树的递归函数。它从末尾到开头遍历 post order 列表,因为这几乎代表了所需的顺序,除了以相反的顺序访问子项:
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])
推荐阅读
- python-3.x - 根据其他列将工作日添加到 pandas df 日期列
- python - 改进一个糟糕的 CNN - 检测图像方向
- php - 将一个图像粘贴到另一个 PHP 时出现问题
- nativescript - Nativescript 6.4.2 iOS webpack 不监视更改
- html - 离子:删除字段下的行
- angularjs - 如何在返回外部可观察对象之前修改可观察对象发出的每个对象的内部元素
- android - 跨 Android API 级别的 SQLite 文件版本兼容性
- python - 将 SQLAlchemy 连接池队列与 Python 多处理一起使用
- html - 防止儿童 div 脱离 CCS-Card
- coldfusion - COLDFUSION:组件 [Document] 没有名称为 [FILENAME] 的可访问成员