如何按目标值把一棵二叉搜索树拆成两棵树？

简化版

按目标值 target 拆分 BST，通常返回两棵树：一棵所有值 <= target，另一棵所有值 > target。递归利用 BST 性质：若根值 <= target，根和左子树都属于小树，只需要拆右子树；若根值 > target，根和右子树都属于大树，只需要拆左子树。

详细版

递归函数 split(root, target) 返回 [small, large]：

如果 root == null，返回 [null, null]；
如果 root.val <= target：
- root.left 一定都 <= root.val <= target，保留在 small；
- 递归拆分 root.right；
- 拆出来的 rightSmall 接回 root.right；
- 返回 [root, rightLarge]。
如果 root.val > target：
- root.right 一定都 > root.val > target，保留在 large；
- 递归拆分 root.left；
- 拆出来的 leftLarge 接回 root.left；
- 返回 [leftSmall, root]。

时间 O(h)，因为每层只沿一条路径递归；空间 O(h)。

完整版教学

一、拆分 BST 到底要保持什么

拆分 BST 不是简单过滤节点，而是要得到两棵仍然合法的 BST。以 target 为界，一棵树保存所有 <= target 的节点，另一棵树保存所有 > target 的节点。节点本身可以复用，通常通过重新连接指针完成，不需要新建所有节点。

例如中序序列是 [1,2,3,4,5,6]，target=3，拆完应该得到 [1,2,3] 和 [4,5,6] 两棵有序结构。树形可能变化，但每棵树内部仍要满足 BST 性质。

记忆钩子：BST 拆分不是按节点逐个搬家，而是沿搜索路径切开，再把切口两侧接回去。

二、为什么每次只递归一边

BST 的根天然把值分成三块：左子树都小于根，根自己，右子树都大于根。若 root.val <= target，那么根和整个左子树都应该进入 small，唯一不确定的是右子树，因为右子树里可能有些值仍然 <= target，有些值 > target。所以只需要拆右子树。

反过来，若 root.val > target，根和整个右子树都应该进入 large，唯一不确定的是左子树。这个性质让时间复杂度不是 O(n)，而是 O(h)，因为我们只沿着一条分界路径走。

三、指针重连怎么理解

假设 root.val <= target，我们拆分 root.right，得到：

rightSmall: 右子树中 <= target 的部分
rightLarge: 右子树中 > target 的部分

因为 rightSmall 中的值都大于 root.val 且不超过 target，所以它应该成为 root 的新右子树。rightLarge 则是最终 large 的一部分。于是返回 [root, rightLarge]。

root(<=target)
├─ left: 全保留
└─ right: split 后只接回 rightSmall

另一种情况完全对称：root.val > target 时，把 leftLarge 接回 root.left，返回 [leftSmall, root]。

四、代码实现

代码短，但返回值含义要非常清楚。这里用长度为 2 的数组表示 [small, large]。

TreeNode[] splitBST(TreeNode root, int target) {
    if (root == null) return new TreeNode[]{null, null};

    if (root.val <= target) {
        TreeNode[] parts = splitBST(root.right, target);
        root.right = parts[0];
        return new TreeNode[]{root, parts[1]};
    } else {
        TreeNode[] parts = splitBST(root.left, target);
        root.left = parts[1];
        return new TreeNode[]{parts[0], root};
    }
}

如果题目定义左边是 < target、右边是 >= target，比较符要从 <= 改成 <，并同步解释边界归属。

五、带数字例子推演

考虑 BST 的中序为 [1,2,3,4,5,6]，根为 4，target=3。因为 4 > 3，根和右子树 [5,6] 都属于 large，只需要拆左子树 [1,2,3]。拆左子树得到 small=[1,2,3]，leftLarge=null，于是把根 4 的左指针接成 null，返回 [1,2,3] 和 [4,5,6]。

当前根	判断	不确定区域	指针动作
4	`> target`	左子树	`root.left = leftLarge`
2	`<= target`	右子树	`root.right = rightSmall`
3	`<= target`	右子树	接回拆出的 small

这个过程像沿着 target 的搜索路径把树切开，切口两侧重新缝合。

六、复杂度为什么是 O(h)

每一层只会递归进入一侧：根值小等于 target 就进右子树，根值大于 target 就进左子树。这和普通 BST 搜索路径一致。平衡树高度 O(log n)，退化树高度 O(n)。

空间复杂度来自递归栈 O(h)。如果用迭代也可以做，但指针重连更难写清，面试中递归版本最直接。注意算法会修改原树结构，如果调用方还需要原树，就必须先复制。

七、常见误区与追问

误区：拆分必须遍历所有节点。 利用 BST 性质后，只需要沿分界搜索路径递归。
追问：为什么 root.val <= target 时左子树不用拆？ 左子树所有值都小于根，也一定 <= target。
误区：拆完可以不重连指针。 不重连会让 small 或 large 仍指向越界节点，破坏结果。
追问：如果边界定义是 < target 和 >= target 怎么改？ 改比较符，并重新说明等于 target 的节点归属。
误区：算法不会改变原树。 它通常原地重连指针，原树结构会被拆开。

八、加强记忆

这题记成「根确定一边，只拆不确定的一边」。根小等于 target 时，根和左子树归 small，拆右子树，把右侧拆出的 small 接回根右边；根大于 target 时，根和右子树归 large，拆左子树，把左侧拆出的 large 接回根左边。返回值永远是 [小树, 大树]，只要这个含义不乱，指针就不会接反。

简化版

详细版