返回信息流看到的一道面试题，网上搜了一下似乎没有很好的答案。
比较容易想到的解法是遍历原二叉树，同时用插入排序法对各元素进行排序，再由这个序列构造一棵查找树出来。但如果希望不用额外空间，仅仅用lChild, rChild指针的重新指向来把原二叉树直接变成查找树，有没有什么好的思路？
这是一条镜像帖。来源：北邮人论坛 / cpp / #85919同步于 2015/3/12
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
普通二叉树如何高效转为二叉查找树
ReLive
2015/3/12镜像同步12 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
比如后续遍历原二叉树，一个一个的拆下来，插入到排序二叉树里。
空间复杂度分析，最差O（n），这是遍历原二叉树需要的空间，插入排序二叉树的空间复杂度是O（1）。
时间复杂度分析，最差O（n^2），比如插入排序二叉树时的序列就是有序的时候。
随即情况下。。不会分析了咯。。
插入排序二叉树的时候，可以插入后调整使得它是平衡的，这样时间复杂度好点吧。。
对呀，我中间那个排序的过程是不必要的，直接各个结点插入到排序二叉树就好啦。
空间复杂度，原二叉树是算法输入，遍历它不能算作算法的复杂度吧，所以我觉得是O(1).
时间复杂度，我们需要遍历原树的n个结点，并把每个结点插入排序二叉树(log n)，所以应该是n.log n吧
【 在 buptxrc 的大作中提到: 】
: 比如后续遍历原二叉树，一个一个的拆下来，插入到排序二叉树里。
: 空间复杂度分析，最差O（n），这是遍历原二叉树需要的空间，插入排序二叉树的空间复杂度是O（1）。
: 时间复杂度分析，最差O（n^2），比如插入排序二叉树时的序列就是有序的时候。
: ...................
即使你写非递归的遍历，栈的最大高度也可能到n。。。算不算无所谓了，反正知道是这样就行～
插入排序二叉树最差是n^2的。例如你插入的序列是1234567。。。那生成的排序二叉树就是一个一直往右下角增长的链表不是吗？
输入序列随机的情况下，时间复杂度我不会分析～
但是我记得knuth好像说 随机序列生成的排序二叉树不会比平衡的排序二叉树的搜索性能低很多，低30%左右。。。至于他说的对错～我就不清楚了～
【 在 ReLive 的大作中提到: 】
: 对呀，我中间那个排序的过程是不必要的，直接各个结点插入到排序二叉树就好啦。
: 空间复杂度，原二叉树是算法输入，遍历它不能算作算法的复杂度吧，所以我觉得是O(1).
: 时间复杂度，我们需要遍历原树的
: .........
【 在 buptxrc 的大作中提到: 】
: 比如后续遍历原二叉树，一个一个的拆下来，插入到排序二叉树里。
: 空间复杂度分析，最差O（n），这是遍历原二叉树需要的空间，插入排序二叉树的空间复杂度是O（1）。
: 时间复杂度分析，最差O（n^2），比如插入排序二叉树时的序列就是有序的时候。
: ...................
学长说的真对!
【 在 inaadversity 的大作中提到: 】
: 把元素排序后，在挂到相应节点上呢 空间O(n) 时间O(NlogN)
nlogn，看来你只能递归的找中点插入了：）
【 在 xuangong 的大作中提到: 】
:
: nlogn，看来你只能递归的找中点插入了：）
不用啊，保持原树的结构不变。遍历把数据放在数组里，排序后再中序遍历原树 挂回。
这也是这种方法的优势，不改变树的结构
【 在 xuangong 的大作中提到: 】
:
: 考虑下有序插入BST的复杂度，所以要计算清楚怎么插
上代码。。。
struct TreeNode
{
int val;
TreeNode *left,*right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
vector<int> l;
int i;
void sorttree1(TreeNode *root){
if(root){
sorttree1(root->left);
l.push_back(root->val);
sorttree1(root->right);
}
}
void sorttree2(TreeNode *root){
if(root){
sorttree2(root->left);
root->val = l[i++];//挂回
sorttree2(root->right);
}
}
void Sorttree(TreeNode * root){
sorttree1(root);
sort(l.begin(),l.end());
sorttree2(root);
}
估计层主说的方法是：
TreeNode * sorttree3(int x,int y){
if(x > y) return NULL;
int mid = (x+y)>>1;
TreeNode *res = new TreeNode(l[mid]);
res->left = sorttree3(x,mid-1);
res->right = sorttree3(mid+1,y);
return res;
}