二叉搜索树中被交换子树的O(n)时间识别算法探究

核心认知澄清 #

• 你提出的“交换两个子树等价于在全局中序序列中交换两个连续子集”的判断是完全准确的，此前无法定位的核心原因，是没有结合树结构的三个固定性质做推导：
  • 任意BST子树的中序遍历结果，在全局中序序列中必然对应一段连续、无交叉的区间，不存在不同子树的遍历片段互相穿插的情况
  • 整棵子树被整体交换位置时，自身内部的节点相对顺序完全保持原样，不会像随机交换数组元素那样打乱块内顺序
  • 两个被交换的子树节点数完全相等，因此对应的中序遍历块长度严格一致

分步实现流程 #

1. 获取全局中序序列
   对当前结构破坏的BST执行一次中序遍历，按遍历顺序将所有节点存入数组inorder_nodes，过程中顺带记录每个节点对应的数组索引位置，单步时间复杂度O(n)。
2. 定位乱序断点
   因为原始中序序列是严格升序的，交换两个等长连续块后的乱序特征是固定的：
   • 从数组左端向右扫描，找到第一处「相邻节点值逆序（前值>后值）」的位置，记为left_break，该位置是第一个被交换块的尾部边界
   • 从数组右端向左扫描，找到第一处「相邻节点值逆序（前值>后值）」的位置，记为right_break，该位置是第二个被交换块的头部边界
   • 结合两个断点位置、两个块等长、块内顺序不变的性质，即可唯一锁定两个被交换块在数组中的精确起止范围，无需依赖原始有序序列做对比。

   验证示例：原始中序序列为[1,2,3,4,5,6,7,8]，交换覆盖节点2、3、4的子树和覆盖节点6、7、8的子树后，乱序序列为[1,6,7,8,5,2,3,4]。左扫找到第一处逆序为索引3（值8）>索引4（值5），右扫找到第一处逆序为索引4（值5）>索引5（值2），最终可锁定两个被交换块分别为索引1-3、索引5-7，和实际交换范围完全匹配。

3. 锁定被交换子树的根节点
   每个被锁定的连续中序区间，必然完整对应某一棵子树的全部节点，只需通过树的父子指针关系定位区间的根节点即可：
   • 从区间两端的节点开始，沿父指针向上回溯，直到找到第一个满足「其中序遍历覆盖范围完全匹配当前锁定区间、无节点溢出区间外」的节点，该节点即为对应被交换子树的根。
   • 全程累计回溯的节点次数不超过O(n)，每个节点最多被访问常数次。

复杂度校验 #

• 全流程仅需1次树的中序遍历、1次数组扫描、累计常数次的父指针回溯，整体时间复杂度严格为O(n)，无超出要求的额外开销。

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