已知二叉树的先序遍历（preorder）和中序遍历（inorder） 或 中序和后序(postorder)，还原该二叉树

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# preorder 先序
# inorder  中序

class Solution(object):
    def buildTree(self, preorder, inorder):
        #如果中序遍历为空，则表示已到达叶节点
        if inorder:
            # 从先序遍历中弹出根节点的值；
            root_val = preorder.pop(0)
            # 从中序遍历中得到根节点在中序遍历中的位置（目的是拆分中序遍历，生成左右子树）；
            root_index = inorder.index(root_val)
            # 生成根节点；
            root = TreeNode(root_val)
            # 递归的生成左右子树
            root.left = self.buildTree(preorder,inorder[:root_index])
            root.right = self.buildTree(preorder,inorder[root_index+1:])
            return root

上述代码完成了利用先序和中序，还原二叉树。

下面介绍利用中序和后序还原二叉树：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        #同样是利用中序是否为空来判断该节点是否为叶节点；
        if inorder:
            root_val = postorder.pop()
            root_index = inorder.index(root_val)
            root = TreeNode(root_val)
            # 利用后序遍历需要在每次迭代中根据root在中序中的位置，对后序遍历的左右子序列拆分，
            # 这样才能方便利用后序遍历的最后一个结点是根结点的特性；
            root.left = self.buildTree(inorder[:root_index],postorder[:root_index])
            root.right = self.buildTree(inorder[root_index+1:],postorder[root_index:])
            return root