LeetCode105：前序中序构造二叉树优化代码出错求排查

给定两个整数数组preorder和inorder，其中preorder是一棵二叉树的前序遍历结果，inorder是同一棵树的中序遍历结果，请构造并返回这棵二叉树。

TreeNode定义：

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

我看到一个简洁的递归解法，但其时间复杂度为O(n²)，因为每次调用都使用了inorder.index()方法查找根节点索引：

class Solution:
    def buildTree(self, preorder, inorder):
        if inorder:
            INDEX = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[INDEX])
            root.left = self.buildTree(preorder, inorder[:INDEX])
            root.right = self.buildTree(preorder, inorder[INDEX+1:])
   
            return root

为了优化索引查找效率，我尝试用哈希表存储中序数组的值与对应索引的映射，写出了如下代码：

class Solution:
    def buildTree(self, preorder, inorder):
        if not inorder or not preorder:
            return None
        
        inorder_map = {value: index for index, value in enumerate(inorder)}
        
        def buildSubTree(preorder, inorder):
            if not inorder or not preorder:
                return None

            root_value = preorder.pop(0)
            root = TreeNode(root_value)

            root_index = inorder_map[root_value]

            root.left = buildSubTree(preorder, inorder[:root_index])
            root.right = buildSubTree(preorder, inorder[root_index + 1:])
            
            return root
        
        return buildSubTree(preorder, inorder)

但这段代码返回错误结果。例如输入：

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

预期构造的二叉树为：

3
       / \
      9   20
         /  \
       15    7

而我的代码构造出的树却是：

3
       / \
      9   20
         /
       15
      /
     7

执行以下验证代码时，本应输出True，实际输出False：

root = Solution().buildTree([3,9,20,15,7], [9,3,15,20,7])
print(root.right.right is not None)  # 预期输出 True

请问我的代码错误在哪里？

内容的提问来源于stack exchange，提问作者Yihan Luo