从给定前序遍历构建BST，可否用普通数组构建方法替代专用方法？求反例

这个问题挺有意思的，得先明确你说的「从数组集合构建BST的常规方法」具体指哪一种，不同的方法结果天差地别：

情况1：常规方法是「按数组顺序逐个插入元素到BST中」 #

这种方法完全可行！

BST的先序遍历序列天然带有「根节点 → 左子树先序 → 右子树先序」的结构特性，而逐个插入的过程刚好契合这个逻辑：

• 第一个元素直接成为根节点；
• 后续属于左子树的元素（全部小于根节点）会被依次插入到根的左子树区域，完美还原原BST左子树的结构；
• 属于右子树的元素（全部大于根节点）则会被插入到根的右子树区域，和原BST的右子树结构完全匹配。

最终构建出的BST和专门针对先序序列的高效构建方法得到的树完全一致，唯一的区别是效率：逐个插入的时间复杂度是O(n²)（最坏情况比如先序序列是递增/递减的，会退化成链表），而专门方法可以做到O(n)或O(nlogn)。

情况2：常规方法是「将数组排序后构建平衡BST」（比如取中间元素为根，递归构建左右子树） #

这种方法完全不可行！

排序操作会直接丢失原先序序列的结构信息，构建出的树和我们需要的原BST完全不是同一棵。

反例演示： #

假设原BST的先序遍历序列是 [5,3,4,7,6]，对应的原BST结构是：

5
   / \
  3   7
   \   \
    4   6

如果用排序法构建：

1. 先将序列排序为 [3,4,5,6,7]；
2. 取中间元素5作为根，左子树处理[3,4]，取4为左子树的根，3作为4的左孩子；右子树处理[6,7]，取7为右子树的根，6作为7的左孩子；
3. 最终得到的BST结构是：

5
   / \
  4   7
 /   /
3   6

这棵树的先序遍历是 [5,4,3,7,6]，和原先序序列[5,3,4,7,6]完全不符，显然不是我们要的目标BST。

内容的提问来源于stack exchange，提问作者csai