Split BST


Time Complexity: O(N), where N is the number of nodes in the input tree, as each node is checked once.
You could also say O(height), right? Your "each node is checked once" sounds so absolute, like that's always the case, not just in worst cases.
And hmm... the Python specification says
rtype: List[TreeNode]
and I always understood that aslist
. But you don't return alist
but atuple
. Does "List
" mean "any kind of list", not justlist
, and doestuple
count as "List
"? That would at least be nonstandard terminology.

@kenteng, isn't this the reason why we are looking around here, eh? this question and delete a node in BST are both convoluted to me. guess just need to think more and adapt to those questions.

this is my solution:
/**
Definition for a binary tree node.

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val = x; }

}
*/
class Solution {
private List<Integer> node_list=new ArrayList<Integer>();
public TreeNode[] splitBST(TreeNode root, int V) {
TreeNode[] result=new TreeNode[2];
inOrder(root);
//corner condition 1:the root is empty
if(node_list.size()==0){
return result;
}
int index=1;
for(int i=0;i<node_list.size();i++){
if(node_list.get(i)>V){
index=i;
break;
}
}
//corner condition 2 first:all the nodes in bst is smaller and equal to V then index==1 or all the nodes in bst is larger than
//V so the index ==0 in both these condition above,we just return the root
if(index==1  index==0){
result[0]=root;
return result;
}
//the normal condition is that the node appears in the middle,so we mark the target val
int val=node_list.get(index1);
//then we find the node and its parent
TreeNode pre=null;
TreeNode p=root;
while(p!=null){
if(p.val==val){
break;
}
else if(p.val>val){
//which mean the val app on the left side of root,in this situation update the pre
pre=p;
p=p.left;
}
else{
//then when the val app on the right side of root
p=p.right;
}
}
if(pre==null){
result[0]=root;
result[1]=root.right;
root.right=null;
return result;
}
result[0]=pre.left;TreeNode temp=p.right; p.right=null; pre.left=temp; result[1]=root; return result;
}
private void inOrder(TreeNode root){
if(root==null){
return;
}
inOrder(root.left);
node_list.add(root.val);
inOrder(root.right);
}
}
