python顺序结构中序与后序序列构建二叉树

Question

python如何用代码由二叉树的中序序列和后序序列构造二叉树，采用顺序存储的方式

Answer 1

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

def buildTree(inorder: List[int], postorder: List[int]) -> TreeNode:
    if not inorder or not postorder:
        return None

    # 在后序遍历中找到根节点
    root_val = postorder[-1]
    root_index = inorder.index(root_val)

    # 递归构造左右子树
    left_inorder = inorder[:root_index]
    right_inorder = inorder[root_index + 1:]
    left_postorder = postorder[:root_index]
    right_postorder = postorder[root_index:-1]
    left_tree = buildTree(left_inorder, left_postorder)
    right_tree = buildTree(right_inorder, right_postorder)

    # 返回构造好的二叉树
    return TreeNode(root_val, left_tree, right_tree)