Leetcode 1050 Solution

This article provides solution to leetcode question 1050 (construct-binary-search-tree-from-preorder-traversal)

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal

Solution

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None
class Solution: def bstFromPreorder(self, preorder: List[int]) -> TreeNode: def dfs(preorder, l, r): if l > r: return None
i = l + 1 while i <= r and preorder[i] < preorder[l]: i += 1
node = TreeNode(preorder[l]) node.left = dfs(preorder, l + 1, i - 1) node.right = dfs(preorder, i, r) return node
return dfs(preorder, 0, len(preorder) - 1)