根据前序序列求根结点，根据中序序列求左右子树。
如上图：根据前序序列，谁在前面谁就是根结点；根据根结点，确定左右子树。
class BiTreeNode:
def __init__(self, data):
self.data = data
self.lchild = None
self.rchild = None
class SolvedPostOrder:
def __init__(self, pre_order, in_order):
self.pre_order = pre_order
self.in_order = in_order
def soled_post_order(self, pre_order, in_order):
if not pre_order:
return None
else:
root = BiTreeNode(pre_order[0])
in_order_root_pos = in_order.index(pre_order[0])
root.lchild = self.soled_post_order(pre_order[1:in_order_root_pos+1], in_order[0:in_order_root_pos])
root.rchild = self.soled_post_order(pre_order[in_order_root_pos+1:], in_order[in_order_root_pos+1:])
return root
def post_order(self, root):
# 后序排列
if root:
self.post_order(root.lchild)
self.post_order(root.rchild)
print(root.data, end='')
def __call__(self):
root = self.soled_post_order(self.pre_order, self.in_order)
self.post_order(root)
while True:
pre_order = input()
in_order = input()
# pre_order = 'ABCDEFG'
# in_order = 'DCBAEFG'
post_order = SolvedPostOrder(pre_order, in_order)
post_order()
print()
