This could be solved recursively. The root princeple is that, for any preorder [a0, a1, a2, ... an], find the smallest j where aj > a0, then a1, a2, ..., a(j-1) is on its left sub-tree and others are on its right sub-tree.
# 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:
return self._helper(0, len(preorder), preorder)
def _helper(self, lo, hi, preorder):
if lo >= hi:
return None
node = TreeNode(preorder[lo])
mid = lo + 1
while mid < hi and preorder[mid] < preorder[lo]:
mid += 1
node.left = self._helper(lo + 1, mid, preorder)
node.right = self._helper(mid, hi, preorder)
return node