Leetcode_1008 Preorder traversal to construct binary search tree

requirements

Returns the root of the binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a type of binary tree where each node satisfies the rule that for any descendant of Node. left, the value is always < node.val, and for any descendant of node.right, the value is always > node.val. In addition, the sequential traversal first displays the value of the node node, then traverses Node. left, then Node. right.

They guarantee that, for a given test case, a binary search tree will always be found.

Example:

Input: [8,5,1,7,10,12] output: [8,5,10,1,7,null,12]Copy the code

The core code

class TreeNode:
    def __init__(self, val=0, left=None, right=None) :
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    def bstFromPreorder(self, preorder: List[int]) - >Optional[TreeNode]:
        inorder = sorted(preorder)
        return self.buildTree(preorder,inorder)
    
    def buildTree(self,preorder,inorder) :
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        left_inorder = inorder[:inorder.index(root.val)]
        right_inorder = inorder[inorder.index(root.val) + 1:]

        l_left = len(left_inorder)
        left_preorder = preorder[1:l_left + 1]
        right_preorder = preorder[l_left + 1:]
        root.left = self.buildTree(left_preorder,left_inorder)
        root.right = self.buildTree(right_preorder,right_inorder)
        return root
Copy the code

We know that the middle order traversal of the binary search tree is sequential, so we can get the corresponding value of the middle order traversal by permutation of the preorder. This is the same as we did before to restore the binary tree according to the preorder and the middle order.