1. Title Description

Returns a given preorder traversal preorder Matching binary search tree （binary search tree） Root node of .

( Think about it , Binary search tree is a kind of binary tree , Each node satisfies the following rules , about node.left Any offspring of , Total value < node.val, and node.right Any offspring of , Total value > node.val. Besides , Preorder traversal first displays the value of the node , Then traverse node.left, Then go through node.right.）

Example ：
Input ：[8,5,1,7,10,12]
Output ：[8,5,10,1,7,null,12]

Tips ：
1 <= preorder.length <= 100
Preface preorder The values in are different .

2. Ideas

Recursion , The key is to find the left subtree and the right subtree's preorder traversal . Because it's a binary search tree , So the value of the left subtree is smaller than the value of the root node , The value of the right subtree is larger than that of the root node . Because it's preorder traversal , So the first node of the array is the root node , Start traversing from the second value of the traversal order , Until the value greater than the root node appears, this section is the order of the left subtree traversal , The rest is the sequence of traversal of the right subtree . recursive .

2.1 Code

class Solution:
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
if len(preorder) == 0:
return None
root = TreeNode(preorder[0])
i = 1
length = len(preorder)
while i < length and preorder[i] < preorder[0] :
i += 1
left = preorder[1:i]
right = preorder[i:]
root.left = self.bstFromPreorder(left)
root.right = self.bstFromPreorder(right)
return root