an Universal solution to any binary tree ! (not only for BST!) ,any better solution ?


  • 0

    O(nlogn) time complexity, travle 2 times ,any better solution ?

      struct my
      {
       public:
     int id;
     int val;
     };
     class Solution {
      public:
       static bool mycmp(my x, my y)
     {
            return x.val>y.val;
      }
    
    int sums[100000];
    vector<my>v;
    int ind;
    
    void init()
    {
        for(int i=0;i<100000;i++)
            sums[i]=0;
        ind=0;
    }
    
    void dfs(TreeNode* r)      //get the data
    {
        if(r==NULL)
         return ;
        my tmp;
        tmp.id=ind++;
        tmp.val=r->val;
        v.push_back(tmp);
        dfs(r->left);
        dfs(r->right);
    }
    
     void dfs1(TreeNode* r)        // plus greater 
    {
        if(r==NULL)
         return ;
        r->val+=sums[ind++];
        dfs1(r->left);
        dfs1(r->right);
    }
    TreeNode* convertBST(TreeNode* root)
    {
        
        init();
        dfs(root);
        sort(v.begin(),v.end(),mycmp);    
        int tmp=0;
        for(int i=1;i<v.size();i++)
        {
             tmp=tmp+v[i-1].val;
            if(v[i].val!=v[i-1].val)
                sums[v[i].id]=tmp;                     //record the prefix sum in the id
            else 
                sums[v[i].id]=sums[v[i-1].id];
        }
        ind=0;
        dfs1(root);
        return root;
    }
    

    };


  • 0

    Is there a O(N) solution?


Log in to reply
 

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