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

• 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;
}
``````

};

• Is there a O(N) solution?

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