Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given


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

Return the following binary tree:


    3
   / \
  9  20
    /  \
   15   7

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        

Solutions:
# 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
         """
         def build(stop):
             if preorder and inorder[-1] != stop:
                 root = TreeNode(preorder.pop())
                 root.left = build(root.val)
                 inorder.pop()
                 root.right = build(stop)
                 return root
             return None # can be skipped
         
         preorder.reverse()
         inorder.reverse()
         return build(None)


 class Solution:
     def buildTree(self, preorder, inorder):
         inorder_dict = {val:index for index,val in enumerate(inorder)}
 
         def buildTreeCore(pre_l, pre_r, in_l, in_r):
             if pre_l == pre_r:
                 return None
 
             root = TreeNode(preorder[pre_l])
             root_inorder_index = inorder_dict[root.val]
             root.left = buildTreeCore(pre_l+1,pre_l+1+root_inorder_index-in_l,\
                                     in_l,root_inorder_index)
             root.right = buildTreeCore(pre_l+1+root_inorder_index-in_l, pre_r,\
                                     root_inorder_index+1,in_r)
             return root
 
         return buildTreeCore(0, len(preorder), 0, len(preorder))

# 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
     """
     lookup = {}
     for i,num in enumerate(inorder):
         lookup[num] = i 
         
     return self.buildrecurtree(lookup, preorder,inorder, 0,0,len(inorder))
 
   def buildrecurtree(self, lookup, preorder, inorder, pre_start, in_start, in_end):
     if (in_start == in_end):
         return None
     node = TreeNode(preorder[pre_start])
     i = lookup[preorder[pre_start]]
     node.left = self.buildrecurtree(lookup, preorder, inorder, pre_start + 1, in_start, i)
     node.right = self.buildrecurtree(lookup, preorder, inorder, pre_start + 1 + i - in_start, i + 1, in_end)
     return node
         

# 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(inorder) == 0:
             return
         #构建元素值为key, index为value的hashmap
         HashMap = {}
         for i in range(len(inorder)):
             HashMap[inorder[i]] = i
         
         root = self.build(HashMap, inorder, 0, len(inorder)-1, preorder, 0, len(preorder)-1)
         return root
     
     def build(self, HashMap, inorder, istart, iend, preorder, pstart, pend):
         if istart>iend or pstart > pend:
             return None
 
         root = TreeNode(preorder[pstart])
         mid_index = HashMap[root.val]
         left_size = mid_index - istart
         right_size = iend - mid_index
         root.left = self.build(HashMap, inorder, istart, mid_index-1, preorder, pstart+1, pstart+left_size)
         root.right = self.build(HashMap, inorder, mid_index+1, iend, preorder, pend-right_size+1, pend)
         return root

# 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 not preorder or not inorder:
             return None
         root = TreeNode(preorder.pop(0))
         index = inorder.index(root.val)
         root.left = self.buildTree(preorder, inorder[:index])
         root.right = self.buildTree(preorder, inorder[index+1:])
         return root
 
 class Solution:
     # @param inorder, a list of integers
     # @param postorder, a list of integers
     # @return a tree node
     # 12:00
     def buildTree(self, preorder, inorder):
         dicinorder = {}
         for i,val in enumerate(inorder):
             dicinorder[val] = i
         start, end = 0, len(inorder)
         return self.helper(start, end, preorder, dicinorder)
     
     def helper(self, start, end, preorder, dicinorder):
         if start == end:
             return None
         root = TreeNode(preorder.pop(0))
         inorderIndex = dicinorder[root.val]
         root.left = self.helper(start, inorderIndex, preorder, dicinorder)
         root.right = self.helper(inorderIndex+1, end, preorder, dicinorder)
         return root

# 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
         """
         INDICES = {}
         for idx, val in enumerate(inorder):
             INDICES[val] = idx
             
         ptr = 0
         def build(left, right):
             nonlocal ptr
             if left > right or right < left or ptr >= len(preorder):
                 return 
             val = preorder[ptr]
 
             node = TreeNode(preorder[ptr])
             ptr += 1
             node.left = build(left, INDICES[val]-1) 
             node.right = build(INDICES[val]+1, right) 
             
             return node
         
         return build(0, len(inorder))
             

# 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 (not preorder):
     #         return None
     #     root_val = preorder[0]
     #     root = TreeNode(root_val)
     #     left_count = inorder.index(root_val)
     #     root.left = self.buildTree(preorder[1:left_count + 1], inorder[:left_count])
     #     root.right = self.buildTree(preorder[left_count + 1:], inorder[left_count + 1:])
     #     return root
         
 
     """
     栈（本题对理解栈的使用很有帮助）
     先序序列：
         1. 如果 preorder[i] 有左子树，那么 preorder[i + 1] 是其左子树的根
         2. 如果 preorder[i] 只有右子树，那么 preorder[i + 1] 是其右子树的根
         3. 如果 preorder[i] 是叶子节点，那么 preorder[i + 1] 是其最深公共祖先的右子树的根
         4. 如果 preorder[i + 1:i + j] 是 preorder[i] 的左子树的节点，那么 preorder[i + j + 1] 是 preorder[i] 的右子树（如果存在的话）的根
     读取先序序列，当不确定节点的左子树是否处理完毕时将节点压栈
     上述操作将保持栈内元素关系：任意时刻，栈内的后入栈元素位于先入栈元素的左子树中
     当元素的左子树已经全部处理完时将其出栈，此时应该继续处理它的右子树（如果存在的话）
     判定元素的左子树是否已经处理完毕，需要中序序列，对于中序序列中的任意元素 j ，其左子树位于 [j - left_count, j - 1] 中
     因此，当栈顶元素等于中序序列的当前元素 j （中序的 [j - left_count, j - 1] 已经处理）时，表明栈顶元素的左子树已经处理完毕， left_count 为 j 的左子树的节点数
     """
     def buildTree(self, preorder, inorder):
         """
         :type preorder: List[int]
         :type inorder: List[int]
         :rtype: TreeNode
         """
         if (not preorder):
             return None
         stack = []
         i, j = 0, 0
         # 先序序列的第一个元素即树的根节点
         root = TreeNode(preorder[0])
         # cur在入栈出栈之间充当了变量传递工作，相当于递归调用的返回值
         cur = root
         stack.append(cur)
         i += 1
         # 循环的本步是否进行出栈操作
         out_stack = False
         # 读取先序序列， preorder[-1] 是最右节点，当这个节点构造完成（ i == len(preorder) ），整颗树就完成了，结束循环
         while (i < len(preorder)):
             if (stack and stack[-1].val == inorder[j]):
                 # 出栈操作，相当于从递归返回
                 # cur 的左子树已经处理完毕
                 # 如果cur有右子树，那么下一步将进入下面的else的if(out_stack)语句块
                 # 如果cur没有右子树，那么下一步将继续进行本语句块的出栈操作
                 cur = stack.pop()
                 out_stack = True
                 j += 1
             else:
                 # 入栈操作，相当于进入递归
                 # cur 的左子树未处理完毕
                 if (out_stack):
                     # 上一步执行了出栈操作，表明cur的左子树已经处理完毕，需要处理其右子树
                     # 相当于进入cur右子树的递归
                     # cur有右子树，preorder[i]是cur右子树的根节点
                     cur.right = TreeNode(preorder[i])
                     cur = cur.right
                 else:
                     # 上一步不是出栈，表明cur的左子树尚未处理
                     # 相当于进入cur左子树的递归
                     cur.left = TreeNode(preorder[i])
                     cur = cur.left
                 stack.append(cur)
                 out_stack = False
                 i += 1
         return root
                     
                 

# 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 (not preorder):
     #         return None
     #     root_val = preorder[0]
     #     root = TreeNode(root_val)
     #     left_count = inorder.index(root_val)
     #     root.left = self.buildTree(preorder[1:left_count + 1], inorder[:left_count])
     #     root.right = self.buildTree(preorder[left_count + 1:], inorder[left_count + 1:])
     #     return root
         
 
     """
     栈
     读取前序序列，当不确定节点的左子树是否处理完毕时将节点压栈
     上述操作将保持栈内元素关系：任意时刻，栈内的后入栈元素位于先入栈元素的左子树中
     当元素的左子树已经全部处理完时将其出栈，此时应该继续处理它的右子树（如果存在的话）
     判定元素的左子树是否已经处理完毕，需要中序序列，对于中序序列中的任意元素 j ，其左子树位于 [0, j - 1] 中
     因此，当栈顶元素等于中序序列的当前元素 j （中序的 [0, j - 1] 已经处理）时，表明栈顶元素的左子树已经处理完毕
     """
     def buildTree(self, preorder, inorder):
         """
         :type preorder: List[int]
         :type inorder: List[int]
         :rtype: TreeNode
         """
         if (not preorder):
             return None
         stack = []
         i, j = 0, 0
         # 前序序列的第一个元素即树的根节点
         root = TreeNode(preorder[0])
         cur = root
         stack.append(cur)
         i += 1
         # 循环的本步是否进行出栈操作
         out_stack = False
         # 读取前序序列， preorder[-1] 是最右节点，当这个节点构造完成（ i == len(preorder) ），整颗树就完成了，结束循环
         while (i < len(preorder)):
             if (stack and stack[-1].val == inorder[j]):
                 # 出栈操作，相当于从递归返回
                 # cur 的左子树已经处理完毕
                 # 如果cur有右子树，那么下一步将进入下面的else的if(out_stack)语句块
                 # 如果cur没有右子树，那么下一步将继续进行本语句块的出栈操作
                 cur = stack.pop()
                 out_stack = True
                 j += 1
             else:
                 # 入栈操作，相当于进入递归
                 # stack[-1] 的左子树未处理完毕
                 if (out_stack):
                     # 上一步执行了出栈操作，表明cur的左子树已经处理完毕，需要处理其右子树
                     # 相当于进入cur右子树的递归
                     # cur有右子树，preorder[i]是cur右子树的根节点
                     cur.right = TreeNode(preorder[i])
                     cur = cur.right
                 else:
                     # 上一步不是出栈，表明cur的左子树尚未处理
                     # 相当于进入cur左子树的递归
                     cur.left = TreeNode(preorder[i])
                     cur = cur.left
                 stack.append(cur)
                 out_stack = False
                 i += 1
         return root
                     
                 

# 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
         """
         null = TreeNode(None)
         max_idx = len(preorder)
         lookups = {}
         
         def _build(parent, p, i):
             print(parent.val, p, i) #REM
             if p >= max_idx:
                 return
             
             node = TreeNode(preorder[p])
             parent.left = node
             print('.. left', node.val) #REM
             lookups[node.val] = node
             
             while p < max_idx and preorder[p] == inorder[i]:
                 
                 while i < max_idx and inorder[i] in lookups:
                     node = lookups[inorder[i]]
                     i += 1
 
                 p += 1
                 
                 if p < max_idx:
                     right = TreeNode(preorder[p])
                     lookups[right.val] = right
                     print('.. right of', node.val, ' -> ', right.val) #REM
                     node.right = right
                     node = right
 
             _build(node, p + 1, i)
         
         _build(null, 0, 0)
         
         return null.left


# 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
         """
         INDICES = {}
         for idx, val in enumerate(inorder):
             INDICES[val] = idx
             
         seen = {}
         ptr = 0
         def build(left, right):
             nonlocal ptr
             print(left, right)
             if left > right or right < left or ptr >= len(preorder):
                 return 
             val = preorder[ptr]
             print(val, left, right)
 
             node = TreeNode(preorder[ptr])
             ptr += 1
             node.left = build(left, INDICES[val]-1) #if (INDICES[val] != 0 and INDICES[val] != len(inorder) - 1) else None
             node.right = build(INDICES[val]+1, right) #if (INDICES[val] != 0 and INDICES[val] != len(inorder) - 1) else None
             
             return node
         
         return build(0, len(inorder))
             

# 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
         """
         preindex = [0]
         ind = {v:i for i, v in enumerate(inorder)}
         head = self.buildTreeCore(0, len(preorder) - 1, preorder, inorder, ind, preindex)
         return head
     
     def buildTreeCore(self, start, end, preorder, inorder, ind,preindex):
         if start <= end:
             mid = ind[preorder[preindex[0]]]
             preindex[0] =preindex[0]+1
             root = TreeNode(inorder[mid])
             root.left = self.buildTreeCore(start, mid - 1, preorder, inorder, ind, preindex)
             root.right = self.buildTreeCore(mid + 1, end, preorder, inorder, ind, preindex)
             return root

# 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(inorder) == 0:
             return
         HashMap = {}
         for i in range(len(inorder)):
             HashMap[inorder[i]] = i
         
         root = self.build(HashMap, inorder, 0, len(inorder)-1, preorder, 0, len(preorder)-1)
         return root
     
     def build(self, HashMap, inorder, istart, iend, preorder, pstart, pend):
         print(istart, iend, pstart, pend)
         if istart>iend or pstart > pend:
             return None
 
         root = TreeNode(preorder[pstart])
         print(root.val)
         mid_index = HashMap[root.val]
         left_size = mid_index - istart
         right_size = iend - mid_index
         root.left = self.build(HashMap, inorder, istart, mid_index-1, preorder, pstart+1, pstart+left_size)
         root.right = self.build(HashMap, inorder, mid_index+1, iend, preorder, pend-right_size+1, pend)
         return root