105、根据前序遍历和中序遍历重构二叉树

假设，在树中没有相同的元素。（方便了定位根节点的index）

1、前序遍历结果的第一个元素是根节点root。

2、中序遍历结果，根节点root的索引是index，在root左边是中序遍历的左子树结果=in_list[0:index]，右边是中序遍历的右子树结果in_list[index+1:]。

3、再来确定前序遍历结果中的左子树与右子树。分析可知，左子树=pre_list[1:index+1],右子树=pre[index+1:]。

4、至此，得到了新的树的前序遍历与中序遍历的结果。于是想到用递归。

概括一下就是，根据前序遍历确定根节点，再确定左子树与右子树的中序遍历结果，确定左子树与右子树的前序遍历结果，再调用函数进行递归即可。

注意index的用法，index属于list的方法，所以list.index(item)即可，item是list中的元素。

原始解法：

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

class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if len(preorder) == 1:
            return TreeNode(preorder[0])
        if len(preorder) == 0:
            return None
        
        #得到根节点
        root_node = TreeNode(preorder[0])
        #只有左子树的情况，删除根节点以后，传入列表
        if preorder[0] == inorder[-1]:
            del(preorder[0])
            del(inorder[-1])
            root_node.left = self.buildTree(preorder,inorder)
            
        #只有右子树的情况，删除根节点以后，传入列表
        elif preorder[0] == inorder[0]:
            del(preorder[0])
            del(inorder[0])
            root_node.right = self.buildTree(preorder,inorder)
            
        else:
            index = inorder.index(preorder[0])
            root_node.left = self.buildTree(preorder[1:1+index],inorder[0:index])
            root_node.right = self.buildTree(preorder[1+index:],inorder[1+index:])
            
        return root_node

参考discuss才知道自己写的比较多了。对于上述代码中，“只有左子树的情况”，”只有右子树的情况“，是可以通过两行代码来解决的，而这行代码包含的思想却不少。

if len(preorder) == 0 and len(inorder) == 0:
     return None

左子树为空意味着什么？

意味着递归中传入左子树中的前序遍历与中序遍历的list是空的。
而list[m:m] == []。（不论m等于多少，即使超过了list的长度。）

比如，若是左子树为空，那么index会为0.那么传入左子树中的前序遍历结果与中序遍历结果都是[1:1],[0:0].都是空。（即使1的索引可能超过了根节点。）于是左子树的递归可以返回None。

因此，上述两行代码，就把上述原始代码中的前两种判断左右子树为空的情况给代替了。下面是最终的代码：

class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if len(preorder) == 0 and len(inorder) == 0:
            return None
        #得到根节点
        root_node = TreeNode(preorder[0])
        index = inorder.index(preorder[0])
        root_node.left = self.buildTree(preorder[1:1+index],inorder[0:index])
        root_node.right = self.buildTree(preorder[1+index:],inorder[1+index:])
            
        return root_node