python但是67大佬救命!2、7、8WA了qaq
查看原帖
python但是67大佬救命!2、7、8WA了qaq
811743
JerryWayne7楼主2023/8/8 16:54
#通过二叉树的中序和前序遍历结果输出后续遍历结果
def build_postorder(preorder,inorder):
    if not preorder or not inorder:
        return []                  #如果输入的两个列表全部为空的话,返回一个空列表,即递归终点

    #根据前序遍历确定根节点
    root_val = preorder[0]
    root_index = inorder.index(root_val)

    #划分左子树和右子树的中序遍历序列
    left_inorder = inorder[:root_index]
    right_inorder = inorder[root_index+1:]

    #根据左子树和右子树的节点个数,分别得到其前序遍历序列
    left_preorder = preorder[1:1 + len(left_inorder)]
    right_preorder = preorder[1 + len(left_inorder):]
    # 递归构建左子树和右子树的后序遍历序列
    left_postorder = build_postorder(left_preorder, left_inorder)
    right_postorder = build_postorder(right_preorder, right_inorder)

    # 合并根节点、左子树的后序遍历序列和右子树的后序遍历序列
    return left_postorder + right_postorder + [root_val]

in_order = list(input())
pre_order = list(input())
post_order = build_postorder(pre_order,in_order)
for i in post_order:
    print(i,end="")
2023/8/8 16:54
加载中...