Construct Binary Tree from Preorder and Inorder Traversal

还是利用分治法，首先必须清楚先序遍历的第一个点就是树的根节点，然后利用这个值在中序序列里面找到坐标，利用此坐标二分递归下去即可，这里用了一个静态变量是为了参数的修改方便

class Solution(object):
    startPreOrder = 0

    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        n = len(preorder)

        return self.helper(preorder, inorder, 0, n)

    def helper(self, preorder, inorder, start, end):
        if start >= end:
            return None

        head = TreeNode(preorder[self.startPreOrder])
        inorderIndex = inorder.index(preorder[self.startPreOrder])
        self.startPreOrder += 1
        head.left = self.helper(preorder, inorder, start, inorderIndex)
        head.right = self.helper(preorder, inorder, inorderIndex + 1, end)
        return head

考虑到这里的index函数实际上是进行了线性搜索，放在O(n)的数据规模里面来看相当于进行了n次O(n)的搜索，可以考虑利用哈希表来cache这里的inorder序列，稍微修改一下，代码变成了下面的样子

class Solution(object):
    startPreOrder = 0
    indexMap = {}

    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        n = len(preorder)
        for i in xrange(n):
            self.indexMap[inorder[i]] = i

        return self.helper(preorder, inorder, 0, n)

    def helper(self, preorder, inorder, start, end):
        if start >= end:
            return None

        head = TreeNode(preorder[self.startPreOrder])
        inorderIndex = self.indexMap[preorder[self.startPreOrder]]
        self.startPreOrder += 1
        head.left = self.helper(preorder, inorder, start, inorderIndex)
        head.right = self.helper(preorder, inorder, inorderIndex + 1, end)
        return head

这里提前用了indexMap对inorder进行哈希，每次需要找到这个数的位置时就只需要O(1)的时间复杂度了

Construct Binary Tree from Inorder and Postorder Traversal

跟上题其实基本一样，不过这里因为是后序遍历，我们需要从队列尾部开始扫描，且对于左孩子右孩子的位置需要交换一下，总体修改很少

class Solution(object):
    startPost = 0
    hashMap = {}

    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        n = len(inorder)
        self.startPost = n - 1
        for i in xrange(n):
            self.hashMap[inorder[i]] = i

        return self.helper(inorder, postorder, 0, n)

    def helper(self, inorder, postorder, start, end):
        if start >= end:
            return None

        head = TreeNode(postorder[self.startPost])
        indexInorder = self.hashMap[postorder[self.startPost]]
        self.startPost -= 1
        head.right = self.helper(inorder, postorder, indexInorder + 1, end)
        head.left = self.helper(inorder, postorder, start, indexInorder)
        return head