求后序遍历

解题思路:

注意事项:

参考代码:

# 定义树节点的数据结构

class TreeNode:

    def __init__(self, val):

        self.val = val

        self.left = None

        self.right = None

# 根据先序遍历和中序遍历构建二叉树

def buildTree(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 = buildTree(preorder[1:root_index+1], inorder[:root_index])

    root.right = buildTree(preorder[root_index+1:], inorder[root_index+1:])

    return root

# 后序遍历二叉树

def postorderTraversal(root):

    if not root:

        return []

    result = []

    result.extend(postorderTraversal(root.left))

    result.extend(postorderTraversal(root.right))

    result.append(root.val)

    return result

# 主函数

def main():

    preorder = input().strip()  # 先序遍历序列

    inorder = input().strip()  # 中序遍历序列

    # 构建二叉树

    root = buildTree(preorder, inorder)

    # 后序遍历二叉树

    result = postorderTraversal(root)

    # 输出后序遍历序列

    print(''.join(result))

# 调用主函数

main()