22158: 根据二叉树前中序序列建树

http://cs101.openjudge.cn/practice/22158/

假设二叉树的节点里包含一个大写字母，每个节点的字母都不同。

给定二叉树的前序遍历序列和中序遍历序列(长度均不超过26)，请输出该二叉树的后序遍历序列

输入

多组数据 每组数据2行，第一行是前序遍历序列，第二行是中序遍历序列

输出

对每组序列建树，输出该树的后序遍历序列

样例输入

DURPA
RUDPA
XTCNB
CTBNX

样例输出

RUAPD
CBNTX

来源：郭炜

也是递归方式处理，利用前序遍历第一个为根节点可以很容易找到跟，进而区分左右子树。

The problem is asking to construct a binary tree from given preorder and inorder traversal sequences, and then output the postorder traversal sequence of the constructed tree.

Here is a step-by-step plan:
1.Create a TreeNode class to represent each node in the tree. 2.Create a function build_tree that takes the preorder and inorder sequences as input and returns the root of the constructed tree. The first character of the preorder sequence is the root of the tree. Find the position of the root in the inorder sequence. Recursively construct the left subtree using the left part of the inorder sequence and the corresponding part of the preorder sequence. Recursively construct the right subtree using the right part of the inorder sequence and the corresponding part of the preorder sequence. 3.Create a function postorder_traversal that takes the root of the tree as input and returns the postorder traversal sequence of the tree. 4.For each pair of preorder and inorder sequences, construct the tree and output the postorder traversal sequence. Here is the Python code that implements this plan:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def build_tree(preorder, inorder):
    if not preorder or not inorder:
        return None
    root_value = preorder[0]
    root = TreeNode(root_value)
    root_index_inorder = inorder.index(root_value)
    root.left = build_tree(preorder[1:1+root_index_inorder], inorder[:root_index_inorder])
    root.right = build_tree(preorder[1+root_index_inorder:], inorder[root_index_inorder+1:])
    return root

def postorder_traversal(root):
    if root is None:
        return ''
    return postorder_traversal(root.left) + postorder_traversal(root.right) + root.value

while True:
    try:
        preorder = input().strip()
        inorder = input().strip()
        root = build_tree(preorder, inorder)
        print(postorder_traversal(root))
    except EOFError:
        break