第三题【先序+后序，求中序】Python实现方法，准确率90%以上，不清楚哪个边界没考虑完全

# 第三题【先序 后序,求中序】Python实现方法,准确率90%以上,不清楚哪个边界没考虑
#
# 返回所求中序序列
# @param n int整型 二叉树节点数量
# @param pre int整型一维数组 前序序列
# @param suf int整型一维数组 后序序列
# @return int整型一维数组
#
class TreeNode:
    # 树的初始化定义，包括值、左节点、右节点
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right

class Solution:
    def Calculation(self, n, pre, suf):
        # 递归过程，逐一分析出节点的值、左子树、右子树
        if len(pre) == 0 and len(suf) == 0:
            return None
        if len(pre) == 1 and len(suf) == 1:
            result = TreeNode(pre[0], None, None)
            return result
        index = suf.index(pre[1])
        left = self.Calculation(index + 1, pre[1:index + 2], suf[:index + 1])
        right = self.Calculation(n - index - 2, pre[index + 2:], suf[index + 1:-1])
        root = TreeNode(pre[0], left, right)
        return root

    def inorderTraversal(self, root):
        # 将Calculation返回的树结构，按照中序排列的列表打印出来
        if root == None:
            return []
        if root.left == None and root.right == None:
            return [root.val]
        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)
        return left + [root.val] + right

    def solve(self, n, pre, suf):
        if len(pre) != n or len(suf) != n:
            return False
        root = self.Calculation(n, pre, suf)
        return self.inorderTraversal(root)