Leetcode 1050 Solution

This article provides solution to leetcode question 1050 (construct-binary-search-tree-from-preorder-traversal)
Categories:
Tags:
Access this page by simply typing in "lcs 1050" in your browser address bar if you have bunnylol configured.

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)