LeetCode 105.从前序与中序遍历序列构造二叉树 解题思路与实现

题目描述：

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \\
  9  20
    /  \\
   15   7

解题思路：

由于前序遍历先访问二叉树的父节点，再访问其左子节点，而中序遍历先访问左子节点再访问父节点。根据这个特点，可知前序遍历数组的第一个元素为树根节点，而在中序遍历数组中，在树根节点前面的元素为该树根节点的左子树，后边的元素为该树根节点的右子树。左子树和右子树也可以用这种方法构造。因此，本题可采用递归的方法，不断的将之前的子树再划分成左子树和右子树。递归结束条件为右子树或者左子树为空。

程序：

class Solution:
    def buildTree(self, preorder, inorder):
        # 为了节省每次遍历列表时间，引入哈希表，存储列表每个元素的下标
        idxMap = {}
        for i in range(len(inorder)):
            idxMap[inorder[i]] = i
        return self.buildNode(preorder, inorder, 0, len(inorder), idxMap)

    def buildNode(self, preorder, inorder, s, e, idxMap):
        # 递归结束条件 子树为空
        if not preorder or s > e:
            return
        # 从列表中取出每棵子树的根节点
        rootVal = preorder.pop(0)
        root = TreeNode(rootVal)
        # 如果子树中只有一个元素，直接返回该节点，不再进行递归
        # if s == e:
        #     return root
        # 递归构造根节点的左右子节点
        root.left = self.buildNode(preorder, inorder, s, idxMap[rootVal] - 1, idxMap)
        root.right = self.buildNode(preorder, inorder, idxMap[rootVal] + 1, e, idxMap)
        return root