from typing import Optional

class TreeNode:
    def __init__(self, val: str):
        self.val = val  # 节点存储的字符值
        self.left = None  # 左子树指针
        self.right = None  # 右子树指针

class BinaryTreeReconstructor:

    # --- 【方法 A】: 前序 + 中序 重建 ---
    # 原理：前序首位是根，中序根在中间，以此切分左右区间
    def buildByPreIn(self, preorder: str, inorder: str) -> Optional[TreeNode]:
        if not preorder or not inorder: return None

        root_val = preorder[0]  # 前序第一个是当前根
        root = TreeNode(root_val)
        idx = inorder.find(root_val)  # 在中序中找到根的位置

        # 递归构建左右子树
        root.left = self.buildByPreIn(preorder[1:idx + 1], inorder[:idx])
        root.right = self.buildByPreIn(preorder[idx + 1:], inorder[idx + 1:])
        return root

    # --- 【方法 B】: 中序 + 后序 重建 ---
    # 原理：后序末位是根，中序根在中间，以此切分左右区间
    def buildByInPost(self, inorder: str, postorder: str) -> Optional[TreeNode]:
        if not inorder or not postorder: return None

        root_val = postorder[-1]  # 后序最后一个是当前根
        root = TreeNode(root_val)
        idx = inorder.find(root_val)  # 在中序中找到根的位置

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

    # --- 【方法 C】: 中序 + 层序 重建 ---
    # 原理：层序第一个是根，通过中序确定左右成员，再过滤层序序列
    def buildByInLevel(self, inorder: str, levelorder: str) -> Optional[TreeNode]:
        if not inorder or not levelorder: return None

        root_val = levelorder[0]  # 层序第一个是根
        root = TreeNode(root_val)
        idx = inorder.find(root_val)

        # 提取属于左子树和右子树的字符集
        left_in = inorder[:idx]
        right_in = inorder[idx + 1:]

        # 关键点：保持层序原有的相对顺序，过滤出子序列
        left_level = "".join([c for c in levelorder if c in left_in])
        right_level = "".join([c for c in levelorder if c in right_in])

        root.left = self.buildByInLevel(left_in, left_level)
        root.right = self.buildByInLevel(right_in, right_level)
        return root

    # --- 【方法 D】: 前序 + 后序 构造 (结果不唯一) ---
    # 原理：假定前序第二个值为左根，在后序中定位以确定左子树范围
    def buildByPrePost(self, preorder: str, postorder: str) -> Optional[TreeNode]:
        if not preorder or not postorder: return None

        root = TreeNode(preorder[0])
        if len(preorder) == 1: return root

        left_root_val = preorder[1]  # 假设前序第二个是左子树的根
        idx = postorder.find(left_root_val)  # 在后序中找到该节点

        # 根据 idx 划分区间递归
        root.left = self.buildByPrePost(preorder[1:idx + 2], postorder[:idx + 1])
        root.right = self.buildByPrePost(preorder[idx + 2:], postorder[idx + 1:-1])
        return root

    # --- 【辅助工具】: 将树转换为层序字符串输出 ---
    # 目的是为了验证重建后的结果是否符合预期的 "ABCDE"
    def to_string(self, root: Optional[TreeNode]) -> str:
        if not root: return "Empty"
        res, queue = [], [root]
        while queue:
            node = queue.pop(0)
            if node:
                res.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
        return "".join(res)


# ==========================================
# 3. 参数调用与验证脚本
# ==========================================
if __name__ == "__main__":
    recon = BinaryTreeReconstructor()

    # 定义测试数据 (对应的树结构：A是根, B是左, C是右, B下挂D、E)
    #      A
    #     / \
    #    B   C
    #   / \
    #  D   E

    pre_data = "ABDE C".replace(" ", "")  # 前序
    in_data = "DBE A C".replace(" ", "")  # 中序
    post_data = "DEB C A".replace(" ", "")  # 后序
    level_data = "ABCDE".replace(" ", "")  # 层序

    # --- 执行四种重建方案 ---
    t1 = recon.buildByPreIn(pre_data, in_data)
    t2 = recon.buildByInPost(in_data, post_data)
    t3 = recon.buildByInLevel(in_data, level_data)
    t4 = recon.buildByPrePost(pre_data, post_data)

    # --- 输出结果 (验证是否都能变回 ABCDE) ---
    print(f"1. 前序+中序 重建后层序输出: {recon.to_string(t1)}")
    print(f"2. 中序+后序 重建后层序输出: {recon.to_string(t2)}")
    print(f"3. 中序+层序 重建后层序输出: {recon.to_string(t3)}")
    print(f"4. 前序+后序 重建后层序输出: {recon.to_string(t4)}")