第一行一个整数 n,表示二叉树的大小。
第二行 n 个整数 a_i,表示二叉树的先序遍历数组。
第三行 n 个整数 b_i,表示二叉树的中序遍历数组。
输出一行 n 个整数表示二叉树的后序遍历数组。
3 1 2 3 2 1 3
2 3 1
数据保证合法
#建立后序遍历序列 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))