Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
It’s guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.
Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Constraints:
# 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.dc(preorder)
def dc(self, pre):
# return condition
if len(pre) == 0:
return None
if len(pre) == 1:
return TreeNode(pre[0])
# main logic
node = TreeNode(pre[0])
pre_l, pre_r = self.bisec(pre[0], pre[1:])
node.left = self.dc(pre_l)
node.right = self.dc(pre_r)
return node
def bisec(self, x, nums):
if nums[-1] < x:
return nums, []
if nums[0] > x:
return [], nums
# if reach here, len(nums) must be at least 2
low = 0
up = len(nums) - 1
while up - low > 1:
mid = low + (up - low) // 2
if nums[mid] < x:
low = mid
if nums[mid] > x:
up = mid
ind = up # index of the start of the 2nd half
return nums[:ind], nums[ind:]