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

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

热度指数：2791 时间限制：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

备注:


数据保证合法

算法知识视频讲解

Python

不知方向的鸵鸟

利用的是根据前序和中序还原树的思路求解的该问题，从右向左还原后序遍历数组

def setPos(preorder, inorder, posorder, si):
    if len(inorder)==0&nbs***bsp;si < 0:
        return si
    data = preorder[0]
    mid = inorder.index(data)
    posorder[si] = data
    si = si-1
    si = setPos(preorder[mid+1:], inorder[mid+1:], posorder, si)
    si = setPos(preorder[1:mid+1], inorder[0:mid], posorder, si)
    return si

n = int(input())
prorder = list(map(int, input().split()))
inorder = list(map(int, input().split()))

posorder = n*['']
s = setPos(prorder, inorder, posorder, n-1)
for i in range(n):
    print(posorder[i], end=' ')

编辑于 2020-04-24 10:55:33 回复(0)

Python

elegantfrog

class Node():
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right

class Tree():
    def reConstructBinaryTree(self, pre, tin):
        if len(pre) == 0:
            return
        root = Node(pre[0])
        TinIndex = tin.index(pre[0])
        root.left = self.reConstructBinaryTree(pre[1: TinIndex+1], tin[0: TinIndex])
        root.right = self.reConstructBinaryTree(pre[TinIndex+1:], tin[TinIndex+1:])
        return root

    def PostTraversal(self, root):
        list1 = []
        if root != None:
            self.PostTraversal(root.left)
            self.PostTraversal(root.right)
            list1.append(root.val)
            print(root.val, end=' ')

if __name__ == '__main__':
    num = int(input())
    pre = list(map(int, input().split()))
    tin = list(map(int, input().split()))
    S = Tree()
    root = S.reConstructBinaryTree(pre, tin)
    S.PostTraversal(root)

发表于 2019-10-08 10:40:59 回复(0)