二叉搜索树（BST）根节点是否必为排序数组中间值？含构建规则问询

核心结论：根节点并非必然是排序数组的中间值 #

举个简单反例：

• 给定数组[1,2,3]，以首个元素1为根构建BST，最终根节点是1；但排序后的数组是[1,2,3]，中间值是2，两者明显不同。
• 再比如数组[3,1,2]，排序后同样是[1,2,3]，根节点是3，也不等于中间值2。

这说明，只要初始选择的根元素（数组首个元素）不是排序数组的中间位置元素，构建出的BST根就不会对应排序数组的中间值。

根节点等于排序数组中间值的场景 #

只有当数组的首个元素恰好是排序数组的中间位置元素时，构建出的BST根节点才会等于排序数组的中间值，具体分两种情况：

• 数组长度为奇数：
  首个元素是排序数组正中间的那个元素（比如长度为5的数组，排序后索引为2的元素）。例如数组[3,1,2,4,5]，排序后是[1,2,3,4,5]，首个元素3是正中间值，以此为根构建BST，根节点自然就是排序数组的中间值。
• 数组长度为偶数：
  排序数组有两个中间元素（比如长度为4的数组，排序后索引为1和2的元素），只要首个元素是这两个中的任意一个，根节点就会是排序数组的中间值之一。例如数组[2,1,3,4]，排序后[1,2,3,4]，首个元素2是左中间值；数组[3,1,2,4]，首个元素3是右中间值，这两种情况的根都对应排序数组的中间元素。

本质上，这种场景的核心是初始根元素在排序数组中的位置处于中间区域，和BST的构建规则无关——构建规则只是保证左小右大的结构，但根的取值完全由初始选择的首个元素决定。

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