1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public TreeNode[] splitBST(TreeNode root, int target) {
        if (root == null) {
            return new TreeNode[] { null, null };
        }
        TreeNode[] ans;
        if (root.val < target) {
            ans = splitBST(root.right, target);
            root.right = ans[0];
            ans[0] = root;
        } else if (root.val > target) {
            ans = splitBST(root.left, target);
            root.left = ans[1];
            ans[1] = root;
        } else {
            TreeNode right = root.right;
            root.right = null;
            ans[0] = root;
            ans[1] = right;
        }
        return ans;
    }
}

思路是这样的. 如果root的值小于val, 那么root以及它的左支都会小于val, 此时我们如果知道root.right代表的树怎么拆分就好了. 把小于val的部分接到root.right这里, 然后大于val的部分就是保留它的样子. 类似地, 如果root的值大于val, 那么root及其它的右支都会大于val, 那么如果我们知道左支的拆分就好了. 大于val的部分就接到root.left, 然后小于val的部分就保留. 如果root的值等于val, 那么root及其左支就是小于等于val的, root的右支就是大于val的, 此时我们直接可以得出答案. 这就是base case.

通过上面的分析, 我们就知道了需要使用递归. 因为target不一定等于树中某个node的值, 因此我们会遇到走到某个地步遇到null的情况. 此时我们直接返回{null, null}即可. 因为到达这个地方要么是node.val > val 或者node.val < val. 此时走到null时, 就表示不需要再继续考虑, 直接让上一层得出答案即可. 上一层如果是node.val > val, 那么它包括右支都是大于val的, 左支是null, 因此小于val的树就是null. 上一层如果是node.val < val, 那么就是它包含左支都是小于val的, 右支是null, 也表示没有值大于val, 因此大于val的树就是null. 如此看来直接返回{null, null}是符合我们上面写的逻辑的.

时间复杂度: O(n)
空间复杂度: O(n)