Python 代码

class TreeNode(object):
    def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None 
class Solution(object):
    def buildTree(self, inorder, postorder):
        if not postorder:
            return None

        root = TreeNode(postorder[-1])    #根节点为后序遍历的末位
        root_index = inorder.index(postorder[-1])   #确定中序遍历中，根节点的下标

        left_i = inorder[:root_index]   #根据根节点下标设立中序遍历的左右子树
        right_i = inorder[root_index+1:]

        len_li = len(left_i) #确定中序遍历左子树的长度

        left_p = postorder[:len_li]     #根据中序遍历左子树长度确定后序遍历的左右子树
        right_p = postorder[len_li:-1]

        root.left = self.buildTree(left_i,left_p)   #递归
        root.right = self.buildTree(right_i,right_p)

        return root

def bfs(root):  #广搜进行层序遍历
    if root == None:
        return
    q = []
    q.append(root)
    head = 0
    while len(q)!=0:
        print(q[head].val,end=' ')

        if q[head].left != None:
            q.append(q[head].left)

        if q[head].right != None:
            q.append(q[head].right)

        q.pop(0)

n = int(input())
posto = list(map(int,input().split()))
ino = list(map(int,input().split()))

solution = Solution()
root = solution.buildTree(ino,posto)
bfs(root)