Leetcode: Construction of binary tree (Python) from forward order and middle order traversal sequence

A good function 2020-11-13 02:53:36
leetcode construction binary tree python

1. Title Description

According to a tree's preorder traversal and middle order traversal structure binary tree .

Be careful :
You can assume that there are no duplicate elements in the tree .

for example , give

The former sequence traversal preorder = [3,9,20,15,7]
In the sequence traversal inorder = [9,3,15,20,7]

3
/ \
9 20
/ \
15 7

2. Ideas

The finger of the sword offer There is such a problem in . Or recursion , According to the characteristics of preorder traversal and medial traversal, we find the sequence of preorder traversal and medial traversal of left subtree , Find the preorder traversal sequence and the middle order traversal sequence of the right subtree . Then recursion .

2. python Code

class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if len(preorder) == 0:
return None
index = inorder.index(preorder)
leftInorder = inorder[:index]
rightInorder = inorder[index+1:]
leftPreorder = preorder[1:len(leftInorder)+1]
rightPreorder = preorder[len(leftInorder)+1:]
root = TreeNode(preorder)
root.left = self.buildTree(leftPreorder,leftInorder)
root.right = self.buildTree(rightPreorder,rightInorder)
return root