题目描述

对一个二叉搜索树，给定一个值V，将这个二叉树分成两个子树，第一个子树的所有结点小于等于V，第二个子树的结点大于V。另外，返回的子树的结构需要保留原始的树结构，也就是祖先-孩子的顺序关系。

样例

input

          4
        /   \
      2      6
     / \    / \
    1   3  5   7

output

          4
        /   \
      3      6      and    2
            / \           /
           5   7         1

算法1

自底向下的遍历 $O(h) h为树高度$

定义一个递归函数dfs，返回一个二维数组ans，当前结点和左右子树被V分割后，ans[0]为小于等于V的部分，ans[1]为大于V的部分。

如果当前结点node大于V，则ans[1]=node，对node的左子树递归调用dfs，得到当前结点左子树的分割结果(一个二维数组nodes)。当前结点的左子树设置为nodes[1],ans[0]设置为nodes[0]

如果当前结点node小于等于V，则ans[0]=node，对node的右子树递归调用dfs，得到当前结点右子树的分割结果(一个二维数组nodes)。当前结点的右子树设置为nodes[0],ans[1]设置为nodes[1]

时间复杂度分析：每次根据当前结点的值选择递归左子树或右子树，时间复杂度为树高度O(h)

Java 代码

class Solution {
    public TreeNode[] splitBST(TreeNode root, int V) {
        TreeNode[] ans = new TreeNode[2];
        return dfs(root, V);
    }

    public TreeNode[] dfs(TreeNode node, int v) {
        TreeNode[] ans = new TreeNode[2];
        if(node==null) return ans;

        if(node.val>v) {
            ans[1] = node;
            TreeNode left = node.left;
            node.left = null;
            TreeNode[] nodes = dfs(left, v);
            node.left = nodes[1];
            ans[0] = nodes[0];
        }else {
            ans[0] = node;
            TreeNode right = node.right;
            node.right = null;
            TreeNode[] nodes = dfs(right, v);
            node.right = nodes[0];
            ans[1]=nodes[1];
        }
        return ans;
    }

}