难度: Medium
给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。
保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。
二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。
二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。
示例 1：
输入：preorder = [8,5,1,7,10,12] 输出：[8,5,10,1,7,null,12]
示例 2:
输入: preorder = [1,3] 输出: [1,null,3]
提示：
1 <= preorder.length <= 1001 <= preorder[i] <= 10^8preorder 中的值 互不相同运行时间: 32 ms
内存: 14.9 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
if len(preorder) == 0:
return None
return self.helper(preorder, 0, len(preorder)-1)
def helper(self, preorder, i, j):
if i > j:
return None
val = preorder[i]
root = TreeNode(val=val)
sep = i+1
while sep <= j and preorder[sep] < val:
sep += 1
root.left = self.helper(preorder, i+1, sep-1)
root.right = self.helper(preorder, sep, j)
return root
首先，我们需要理解前序遍历的特点，即首个元素是树的根节点，其后是左子树的节点和右子树的节点。这个题解使用递归的方法，首先将根节点从前序遍历的首个元素建立，然后寻找左子树和右子树的分界点（即第一个大于根节点的元素），再对左右子树递归地进行同样的构建过程。这样，我们可以保证每次递归都正确地构建出左右子树。
时间复杂度: O(n^2)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
if len(preorder) == 0:
return None
return self.helper(preorder, 0, len(preorder)-1)
def helper(self, preorder, i, j):
if i > j:
return None
val = preorder[i]
root = TreeNode(val=val) # 创建根节点
sep = i+1
while sep <= j and preorder[sep] < val: # 寻找比根节点大的第一个元素的索引
sep += 1
root.left = self.helper(preorder, i+1, sep-1) # 递归构建左子树
root.right = self.helper(preorder, sep, j) # 递归构建右子树
return root
当输入的前序遍历结果是一个已经排序的数组时，例如 [1, 2, 3, 4, 5]，每次递归调用都会将下一个元素作为树的右子节点，而没有左子节点。这将导致构造出的二叉搜索树退化成一个链状结构，即每个节点都只有右子节点。在这种情况下，递归的深度等于数组的长度，若数组长度很大，可能会导致递归栈溢出，从而影响算法的性能和稳定性。
可以通过使用额外的数据结构如栈来模拟递归过程，从而避免深度递归带来的栈溢出问题。此外，可以维护一个全局索引指针，而非每次递归传递新的索引范围，这样可以避免重复的边界计算。另一种改进方式是使用哈希表或平衡二叉树来快速定位右子树的开始位置，减少每次寻找分界点的时间复杂度。
在每次递归调用中，通过选择数组中的当前元素作为根节点，并找到第一个大于根节点的元素的位置，从而确定左子树和右子树的范围。这种方法根据二叉搜索树的性质，即左子树的所有元素小于根节点，右子树的所有元素大于根节点，保证了每次递归都能正确地构建每个子树的根节点。
是的，对于非常大的输入数组，由于递归深度可能会非常高，尤其是在数组已经排序等极端情况下，题解中的递归方法可能会导致栈溢出。为了防止这种情况，可以考虑使用迭代法而非递归，或者在编程时使用尾递归优化。此外，可以将递归转换为使用显式栈的迭代方法，这样可以手动控制栈的使用，从而避免系统栈溢出的风险。