SplitBST [source code]
public class SplitBST {
static
/******************************************************************************/
class Solution {
public TreeNode[] splitBST(TreeNode root, int V) {
TreeNode small_root = new TreeNode (0), big_root = new TreeNode (0);
TreeNode cur = root, cur_small = small_root, cur_big = big_root;
while (cur != null) {
if (cur.val <= V) {
cur_small.right = cur;
cur_small = cur;
TreeNode right = cur.right;
cur.right = null;
cur = right;
} else {
cur_big.left = cur;
cur_big = cur;
TreeNode left = cur.left;
cur.left = null;
cur = left;
}
}
return new TreeNode[] {small_root.right, big_root.left};
}
}
/******************************************************************************/
public static void main(String[] args) {
SplitBST.Solution tester = new SplitBST.Solution();
}
}
contest的时候本着笨办法好过没办法的思路, 写了这个代码:
class Solution {
TreeNode[] res;
public TreeNode[] splitBST(TreeNode root, int V) {
res = new TreeNode[2];
if (contains (root, V)) {
dfs (root, root, null, V);
}
}
void dfs_hit (TreeNode node, TreeNode root, TreeNode parent, int target) {
// pre-leaf prevents null pointer
if (node.val == target) {
if (parent != null) {
parent.left = node.right;
}
node.right = null;
if (node.val < root.val) {
res[0] = node;
res[1] = root;
} else {
res[0] = root;
res[1] = node;
}
return;
}
TreeNode next = target < node.val ? node.left : node.right;
if (next != null)
dfs (next, root, node, target);
else {
if (target < root.val) {
if (target < node.val) {
res[0] = null;
res[1] = root;
} else {
res[0] = node;
if (parent != null)
parent.left = null;
res[1] = root;
}
} else {
if (target < node.val) {
res[0] = root;
res[1] = root.right;
} else {
}
}
}
}
boolean contains (TreeNode root, int target) {
if (root == null)
return false;
TreeNode cur = root;
while (cur != null) {
if (cur.val == target)
return true;
cur = target < cur.val ? cur.left : cur.right;
}
return false;
}
}
但是最后实际上是没有写完的; 而且写的这么复杂的时候, 大概已经有点怀疑走错方向了; 后来大概看了一下contest里面的其他解法, 总结一个之前忘记的问题;
以前写recursion或者DFS的时候, 总是喜欢考虑用void mutation的操作方式来完成, 认为这样的方法更加的方便; 但是这一题可以看到, 这种方式的recursion并不总是最优秀的;
mutating recursion vs. returned recursion
这题后面看到的一些contest解法, 用的很多都是returned recursion; 我这里上面这个失败的代码的思路, 其实更多的是一个通过甚至类似循环的操作; 一般来说, mutating的recursion跟imperative的做法非常近似, 而returned recursion更多的时候更加的declarative, 更加注重于对于root level decision和peel head的操作; 这个时候还没有代码还不好说, 后面配合代码说这个问题;
也不是说哪种方法就一定行, 另外一种就一定不行, 毕竟之前做题的时候也碰到过不少有些时候用这个好有些时候用那个好的情况; 我想说的观点是, 假如一个新方法, 知道用recursion来做(毕竟BST), 但是用一个思路卡住了, 可以尝试转换一下思路;
根据一个discussion改写的代码, 速度是3ms (NA).
editorial
Approach #1: Recursion [Accepted]
Intuition and Algorithm
The root node either belongs to the first half or the second half. Let's say it belongs to the first half.
Then, because the given tree is a binary search tree (BST), the entire subtree at root.left must be in the first half. However, the subtree at root.right may have nodes in either halves, so it needs to be split.
Diagram of tree being split
In the diagram above, the thick lines represent the main child relationships between the nodes, while the thinner colored lines represent the subtrees after the split.
Lets say our secondary answer bns = split(root.right) is the result of such a split. Recall that bns[0] and bns[1] will both be BSTs on either side of the split. The left half of bns must be in the first half, and it must be to the right of root for the first half to remain a BST. The right half of bns is the right half in the final answer.
Diagram of how root tree connects to split of subtree at root.right
The diagram above explains how we merge the two halves of split(root.right) with the main tree, and illustrates the line of code root.right = bns[0] in the implementations.
class Solution {
public TreeNode[] splitBST(TreeNode root, int V) {
if (root == null)
return new TreeNode[]{null, null};
else if (root.val <= V) {
TreeNode[] bns = splitBST(root.right, V);
root.right = bns[0];
bns[0] = root;
return bns;
} else {
TreeNode[] bns = splitBST(root.left, V);
root.left = bns[1];
bns[1] = root;
return bns;
}
}
}
可以看到这个算法本身写起来非常的简单; 就是从declarative的角度, 用最直接的root level decision完成的; 没有什么好说的; 这个复杂度是O(N), 但是因为是BST, 其实也可以认为是O(H).
@blackspinner said in [C++]Easy recursion in O(n):
Let
res[0]be tree less than or equal to V,res[1]be tree greater than V.Detailed explanation: First of all, we can see that the given root is always there in the answer (either in the bigger subtree or in the smaller subtree). After that, if
root->val > V, there is a chance that there is some subtree within the subtreeroot->leftwhich maybe greater than V and that subtree needs to be attached toroot->left. Now, we see that this problem of finding "subtree inroot->leftwhich is greater than V" is the same as the current problem of splittingroot. So we can recurse on left and get the required results. One thing to worry about is, what if there is no subtree inroot->leftthat is greater than V? This case is handled automatically by the base case.
Similar argument applies for the caseroot->val <= V.
vector<TreeNode*> splitBST(TreeNode* root, int V) {
vector<TreeNode *> res(2, NULL);
if(root == NULL) return res;
if(root->val > V){
res[1] = root;
auto res1 = splitBST(root->left, V);
root->left = res1[1];
res[0]=res1[0];
}else{
res[0] = root;
auto res1 = splitBST(root->right, V);
root->right = res1[0];
res[1] = res1[1];
}
return res;
}
@blackspinner said in [C++]Easy recursion in O(n):
I will try to explain my thought process, hopefully this will give you some insight.
First of all, we can see that the given root is always there in the answer (either in the bigger subtree or in the smaller subtree). After that, if
root->val > V, there is a chance that there is some subtree within the subtreeroot->leftwhich maybe greater than V and that subtree needs to be attached toroot->left. Now, we see that this problem of finding "subtree inroot->leftwhich is greater than V" is the same as the current problem of splittingroot. So we can recurse on left and get the required results. One thing to worry about is, what if there is no subtree inroot->leftthat is greater than V? This case is handled automatically base case.
Similar argument applies forroot->val <= V.Also a big hint for me was to ignore the part of the question that said return the 2 subtrees in any order (that was there to confuse people I think) which I did pretty late.
@tyuan73 said in Recursive JAVA solution:
public TreeNode[] splitBST(TreeNode root, int V) {
TreeNode sP = new TreeNode(0), bP = new TreeNode(0);
split(root, V, sP, bP);
return new TreeNode[]{sP.right, bP.left};
}
private void split(TreeNode node, int v, TreeNode sP, TreeNode bP) {
if (node == null) return;
if (node.val <= v) {
sP.right = node;
TreeNode right = node.right;
node.right = null;
split(right, v, node, bP);
} else {
bP.left = node;
TreeNode left = node.left;
node.left = null;
split(left, v, sP, node);
}
}
首先说一下, 这题并不简单, 之前contest结束的时候就看到, 其实很多人花的时间最多的就是这一题;
我之前在上面说过, 这题的大部分的做法都是declarative returned recursion来做的; 但是这里这个老师的这个做法则是用我自己没有成功的imperative mutating recursion来做的; 大概思考了一下, 感觉还是我自己没有找到合理的设计就开始直接用最naive的思路去写, 最后自然是越写越乱;
上面这个做法, 我自己给改写成了一个iteration, 因为他这个recursion其实就是从上到下跑一遍就完了:
class Solution {
public TreeNode[] splitBST(TreeNode root, int V) {
TreeNode small_root = new TreeNode (0), big_root = new TreeNode (0);
TreeNode cur = root, cur_small = small_root, cur_big = big_root;
while (cur != null) {
if (cur.val <= V) {
cur_small.right = cur;
cur_small = cur;
TreeNode right = cur.right;
cur.right = null;
cur = right;
} else {
cur_big.left = cur;
cur_big = cur;
TreeNode left = cur.left;
cur.left = null;
cur = left;
}
}
return new TreeNode[] {small_root.right, big_root.left};
}
}
顺便提一下, 为什么这个算法不需要recursion? 因为你要思考一下, 究竟什么情况下你才需要recursion?
- 不清楚iteration的level层数的上限; 比如N-sum问题;
- 需要倒退到之前的iteration进行undo: 这个iteration就是完全无法解决的了;
但是这里的这个算法, 完全都不需要这两个功能;
理解这个算法, 你可以举一个[4,2,8,1,3,6,9,null,null,null,null,5,7] split 6.5的例子;
通过这个例子你可以看出来, 假如你画一条线代表这个split, 那么最后真正需要被破坏的edge就是这条线穿过的这些edge; 然后最后真正最受影响的node就是这些edge的end; 他这里用两个dummy来收集这些end, 并且保持order; 因为我们是一个从上到下的iteration, 所以small这边始终是往right的方向append, 而big这边始终是往left append;
讲实话我也不是很确定怎么才能相处这样一个用两个accum来collect的思路, 也许这个就是split问题的一个通用解法? 之前有一个split LinkedList的题目好像也用过类似的做法;
没有submission, 懒得看contest;
Problem Description
Given a Binary Search Tree (BST) with root node root, and a target value V, split the tree into two subtrees where one subtree has nodes that are all smaller or equal to the target value, while the other subtree has all nodes that are greater than the target value. It's not necessarily the case that the tree contains a node with value V.
Additionally, most of the structure of the original tree should remain. Formally, for any child C with parent P in the original tree, if they are both in the same subtree after the split, then node C should still have the parent P.
You should output the root TreeNode of both subtrees after splitting, in any order.
Example 1:
Input: root = [4,2,6,1,3,5,7], V = 2
Output: [[2,1],[4,3,6,null,null,5,7]]
Explanation:
Note that root, output[0], and output[1] are TreeNode objects, not arrays.
The given tree [4,2,6,1,3,5,7] is represented by the following diagram:
4
/ \
2 6
/ \ / \
1 3 5 7
while the diagrams for the outputs are:
4
/ \
3 6 and 2
/ \ /
5 7 1
Note:
- The size of the BST will not exceed 50.
- The BST is always valid and each node's value is different.
Difficulty:Medium
Total Accepted:1.1K
Total Submissions:2.6K
Contributor:fishercoder
Companies
amazoncoupang
Related Topics
binary search tree
Similar Questions
Delete Node in a BST
Hint 1
Use recursion. If root.val <= V, you split root.right into two halves, then join it's left half back on root.right.