Split BST


  • 0

    Click here to see the full article post


  • 1

    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 as list. But you don't return a list but a tuple. Does "List" mean "any kind of list", not just list, and does tuple count as "List"? That would at least be non-standard terminology.


  • 0
    K

    Why is this problem medium? It is so convoluted. If given at an interview, I don't think I can write out clear codes like this.


  • 0

    @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.


  • 0
    X

    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(index-1);
      //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);
      }
      }


  • 0
    P

    Very clear! Nice work awice!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.