将满二叉树转换为求和二叉树

class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None
# 创建solution class，里面包含了两个方法：
# createTree：根据preorder和inorder创建一棵求和树
# inorder：先序遍历求和树
class Solution:
    # 求和树的方法就是找到根节点，然后对左右子树求和，接下来递归调用就可以
    def createSumTree(self, preOrder, inOrder):
        # 递归的边界条件,当只有一个节点的时候，求和树的root为0
        # 不为0 的时候，root和等于preorder的从第一个元素开始的列表求和
        if len(preOrder) == 0:
            return None
        if len(preOrder) == 1:
            root = TreeNode(0)
        else:
            root = TreeNode(sum(preOrder[1:]))
        # 开始递归，分别对左子树递归生成树，右子树递归生成树，就需要找到左子树和右子树的
        # preOrder 和inOrder的序列开始结束项目
        # 首先就是需要找到根节点在inOrder里面的位置，从此可以用preOrder里面分离出左子树和右子树
        root_index = inOrder.index(preOrder[0])
        # 分离出preorder的左子树和右子树
        pre_left = preOrder[1:root_index+1]
        pre_right = preOrder[root_index+1:]
        # 递归调用createSumTree
        root.left = self.createSumTree(pre_left, inOrder[0:root_index])
        root.right = self.createSumTree(pre_right, inOrder[root_index+1:])
        return root
    def midTreverse(self,root):
        if root == None:
            return []
        return self.midTreverse(root.left) + [root.val] + self.midTreverse(root.right)
s = Solution()
preOrder = list(map(int,input().strip().split()))
midOrder = list(map(int,input().strip().split()))
root = s.createSumTree(preOrder,midOrder)
print(" ".join(list(map(str,s.midTreverse(root)))))