q****x
发帖数: 7404 | 1 有没有可能inplace？
1. 利用二叉树指针空间，把二叉树转成两个排序双链表。
2. 合并两个链表。
3. 将排序双链表转成二叉树。
不过这样似乎很无聊。时间O(nlogn)空间O(1)，和一个个插入一回事。 |
g*********8
发帖数: 64 | 2 好像见过几个面试题要求inplace，我只能想出一样的解法了 |
s******n
发帖数: 3946 | 3 应该充分利用排序的特性，假设第二颗树序列为n1,n2,n3....
n1插入第一颗树后，n2不用从顶端开始查，可以从n1插入位置开始向上搜索（前提是每
个node都有parent指针） |
s******n
发帖数: 226 | 4 void merge(node* root1, node* root2){
int count =0;
node* cur = root1;
for(;cur;cur = cur->right, count++)
while(rightRotate(cur));
cur = root2;
for(;cur;cur = cur->right, count++)
while(rightRotate(cur));
// Merge 2 linked list in place
for(int i=count/2;i;i = i/2){
cur = root;
for(int j=0;j
leftRotate(cur);
cur = cur->right;
}
}
} |
l*****n
发帖数: 577 | 5 what does right/leftRotate do?
【在 s******n 的大作中提到】
: void merge(node* root1, node* root2){
: int count =0;
: node* cur = root1;
: for(;cur;cur = cur->right, count++)
: while(rightRotate(cur));
: cur = root2;
: for(;cur;cur = cur->right, count++)
: while(rightRotate(cur));
: // Merge 2 linked list in place
: for(int i=count/2;i;i = i/2){
|
s******n
发帖数: 226 | 6 Left rotate
bool left(node* root){
If !root or !root-right
Return 0
Node* n = root-right
Root-right = n-right
N-right = n-left
N-left = root-left
Root-left = n
Swap n and root's Val
Return 1
Right rotate similar |
