张芷铭的个人博客

二叉树

给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。

输入描述

输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。

输出描述

对于每组输入，输出对应的二叉树的后续遍历结果。

输入示例
DBACEGF ABCDEFG
BCAD CBAD
输出示例
ACBFGED
CDAB
答案
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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

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

def postorder_traversal(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]

while True:
    try:
        preorder, inorder = input().split()
        root = build_tree(preorder, inorder)
        postorder = postorder_traversal(root)
        print(''.join(postorder))
    except EOFError:
        break

💬 评论