求后序遍历（python）

解题思路:

注意事项:

参考代码:

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)

    # 切分左子树的中序遍历序列和右子树的中序遍历序列

    left_inorder = inorder[:root_index]

    right_inorder = inorder[root_index + 1:]

    # 切分左子树的先序遍历序列和右子树的先序遍历序列

    left_preorder = preorder[1:1 + len(left_inorder)]

    right_preorder = preorder[1 + len(left_inorder):]

    # 递归构建左子树和右子树

    root.left = build_tree(left_preorder, left_inorder)

    root.right = build_tree(right_preorder, right_inorder)

    return root

def postorder_traversal(root):

    if not root:

        return []

    result = []

    # 递归后序遍历左子树

    result.extend(postorder_traversal(root.left))

    # 递归后序遍历右子树

    result.extend(postorder_traversal(root.right))

    # 将根节点加入结果列表

    result.append(root.val)

    return result

# 定义二叉树节点类

class TreeNode:

    def __init__(self, val=0, left=None, right=None):

        self.val = val

        self.left = left

        self.right = right

# 读取输入

preorder = input().strip()

inorder = input().strip()

# 构建二叉树

root = build_tree(preorder, inorder)

# 后序遍历

result = postorder_traversal(root)

# 输出结果

print(''.join(result))