题解 | #从中序与后序遍历序列构造二叉树#

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param inorder int整型一维数组 中序遍历序列
# @param postorder int整型一维数组 后序遍历序列
# @return TreeNode类
#
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder or not postorder:
            return None

        # 后序遍历的最后一个元素为根节点
        root_val = postorder[-1]
        root = TreeNode(root_val)

        # 在中序遍历中找到根节点的位置
        inorder_index = inorder.index(root_val)

        # 递归构建左子树和右子树
        root.left = self.buildTree(inorder[:inorder_index], postorder[:inorder_index])
        root.right = self.buildTree(
            inorder[inorder_index + 1 :], postorder[inorder_index:-1]
        )

        return root

    # 层次遍历二叉树并转化为形式化字符串


    def treeToString(root):
        if not root:
            return "{}"

        result = []
        queue = [root]

        while queue:
            node = queue.pop(0)
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append("#")

        # 去掉末尾多余的'#'
        while result[-1] == "#":
            result.pop()

        return "{" + ",".join(result) + "}"