通过先序和中序数组生成后序数组

[编程题]通过先序和中序数组生成后序数组

热度指数：2824 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一棵二叉树的先序和中序数组，通过这两个数组直接生成正确的后序数组。

输入描述:

第一行一个整数 n，表示二叉树的大小。

第二行 n 个整数 a_i，表示二叉树的先序遍历数组。

第三行 n 个整数 b_i，表示二叉树的中序遍历数组。

输出描述:

输出一行 n 个整数表示二叉树的后序遍历数组。

示例1

输入

3
1 2 3
2 1 3

输出

2 3 1

备注:


数据保证合法

算法知识视频讲解

Python3

毓毓子最可爱

#建立后序遍历序列
def getLast(pre, mid):
    #如果只有一个节点
    #直接返回
    if len(pre) <= 1:
        return pre
    #先序遍历的第一个节点是根节点
    root = pre[0]
    #划分左右子树
    index = mid.index(root)
    preLeft = pre[1:index + 1]
    preRight = pre[index + 1:]
    midLeft = mid[:index]
    midRight = mid[index + 1:]
    #后序遍历的顺序是左右根
    return getLast(preLeft, midLeft) + getLast(preRight, midRight) + [root]

if __name__ == '__main__':
    #读入数据
    n = int(input())
    pre = input()
    pre = pre.split()
    mid = input()
    mid = mid.split()
    #建立后序遍历序列
    last = getLast(pre, mid)
    print(' '.join(last))

发表于 2021-08-06 08:57:17 回复(0)