title
返回与给定前序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，前序遍历首先显示节点 node 的值，然后遍历 node.left，接着遍历 node.right。）
题目保证，对于给定的测试用例，总能找到满足要求的二叉搜索树。
示例：
输入：[8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]
提示：
1 <= preorder.length <= 1001 <= preorder[i] <= 10^8preorder中的值互不相同
solution
lower, upper的思想，常见于bst相关算法里
时间复杂度：O(n)
class Solution:
idx = 0
preorder = []
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
self.idx = 0
self.preorder = preorder
return self.helper(float('-inf'), float('inf'))
def helper(self, lower, upper) -> TreeNode:
if not self.preorder or self.idx >= len(self.preorder):
return None
val = self.preorder[self.idx]
if not lower <= val <= upper:
return None
root = TreeNode(val)
self.idx += 1
root.left = self.helper(lower, val)
root.right = self.helper(val, upper)
return root
o(nlogn)的
class Solution:
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
if not preorder:
return None
elif len(preorder) == 1:
return TreeNode(preorder[0])
root = TreeNode(preorder[0])
rightStart = 0
for i in range(1, len(preorder)):
if preorder[i] > preorder[0]:
rightStart = i
break
if rightStart == 0:
root.left = self.bstFromPreorder(preorder[1:])
elif rightStart == 1:
root.right = self.bstFromPreorder(preorder[1:])
else:
root.left = self.bstFromPreorder(preorder[1:rightStart])
root.right = self.bstFromPreorder(preorder[rightStart:])
return root