遍历 bfs,按从左到右遍历
先根遍历(第一次遇到就输出) 中根遍历(第二次遇到) 后根遍历(最后一次遇到)
# 已知中序和后序遍历的结果,求前序遍历的结果
def pre_spell(mid: list, end: list):
if len(mid) == 0:
return
root = end[-1]
print(root, end="")
index = mid.index(root)
pre_spell(mid[:index], end[:index])
pre_spell(mid[index + 1:], end[index:-1])
pre_spell(mid, end)