w***o
发帖数: 109 | 1 看到很多解法都是in-order遍历两个BST，merge两个array，然后再重构BST，为什么这
么啰嗦？
不能这样直接merge吗？基本思想就是，比较root1和root2，如果root2大的话，把
root2断为两个子树，一个的根是root2的左孩子，另一个是root2及其右子树。把root2
及其右子树与root1的右子树合并，把root2的左孩子与root1继续合并：
Node mergeBST(Node root1, Node root2) {
if (root1 == null || root2 == null)
return root1 == null? root2 : root1;
if (root1.data <= root2.data)
{
Node left = root2.left;
root2.left = null;
root1.right = mergeBST(root1.right, root2);
root1 = mergeBST(roo... 阅读全帖 |
|
a*****y
发帖数: 22 | 2 bool IsIdenticalTree(const Node* root1, const Node* root2) {
if (root1 && !root2) {
return false;
} else if (!root1 && root2) {
return false;
} else if (!root1 && !root2) {
return true;
} else if (root1->data != root2->data) {
return false;
} else if (root1->next.size() != root2->next.size()) {
return false;
}
for (int i = 0; i < root1->next.size(); ++i) {
if (!IsIdenticalTree(root1->next[i], root2->next[i])) {
return false;
}
}
return true;
}
... 阅读全帖 |
|
n*****g
发帖数: 16 | 3 感觉你那个merge 2 BST的程序有点问题。看看下面这个code：
Node* MostLeft(Node *root)
{
if(root->left == NULL)
return root;
else
return MostLeft(root);
}
// Merge two BST in to one BST.
Node* MergeTwoBST(Node* root1, Node* root2)
{
Node *left, *right, *mostLeft;
if(root1 == NULL)
return root2;
if(root2 == NULL)
return root1;
if(root1->value > root2->value)
return MergeTwoBST(root2, root1);
if(root1->value < root2->value)
{
right = root1->r |
|
s******t
发帖数: 2374 | 4 Mmmm....let me write one:
list1:
1-> 2-> 3->4
list2:
5->6->3->4
int countlen(Node node){
int counter = 0;
while(node!=null) {node=node->next; counter++;}
return counter;
}
Node goNstep(Node root, int n){
while(n-->0) root=root->next;
return root;
}
Node getCommon(Node root1, Node root2){
int len1 = countlen(root1);
int len2 = countlen(root2);
if(len1 > len2) root1 = goNstep(root1, len1-len2);
else root2 = goNstep(root2, len2-len1);
while(root1!=NULL){
if(root1 == root2) brea |
|
g*********s
发帖数: 1782 | 5 2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
时间复杂度，如何优化。
recursion?
is_equal(root1, root1) ::= root1->dat == root2->dat &&
(is_equal(root1->left, root2.left) && is_equal(root1->right, root1-
>right || ... //swap case).
each node can at most trigger 2 swap ops. so worst case 2n? not sure if
a swap on one parent and a swap on its kid would cancel each other.
complexity exponential?
optimization: traverse the tree to calculate the size of each sub-tree.
check the sub-tree size before recursive call.
3.... 阅读全帖 |
|
w***o
发帖数: 109 | 6 当然没有假定root2左树中的所有node比root1小.
所以我才用
root1 = mergeBST(root1, left);
而不是：
root1.left = mergeBST(root1.left, left); |
|
a********8
发帖数: 1625 | 7 第一步是计算query point到root1的距离，把它作为best_value,然后搜索root1的两边
,此时不能排除右边。
先搜左边，发现query point到root2的距离更小，update,但是并不能小于query point
到root1所划分的分割线，所有root1的右边还得接着搜（否则可以直接扔掉右边）
这样可以达到LogN的时间复杂度 |
|
s******n
发帖数: 226 | 8 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;
}
}
} |
|
t*****g
发帖数: 6101 | 9 盼富就这傻屄肏性
比如那个root1系列，比邓小平的亲孙子还多情。 |
|
t*****g
发帖数: 6101 | 10 有个极端邓轮是root1，2，3系列，最近自杀了很多马甲，这个人出口成脏
和老将的极品一个风格。 |
|
d******e
发帖数: 196 | 11 听说cynica和root1,2,3,4,5关一个笼子里，我很担心 |
|
|
|
k**********4
发帖数: 16092 | 14 抓了也没用，床铺知道可能反而很高兴。现在这的几个左b，sgraster,youhi还有root1
，可能都是gay, 都对床铺恨之入骨 |
|
q********u
发帖数: 15519 | 15 抓捕库克的目的是打压苹果，和川普没关心系。
抓捕孟公主与川普无干。
: 抓了也没用，床铺知道可能反而很高兴。现在这的几个左b，sgraster,youhi还
有root1
: ，可能都是gay, 都对床铺恨之入骨
|
|
s******t
发帖数: 2374 | 16 这个主要是要比较reference儿不是比较content吧。
while(root1 == root2) |
|
g****y
发帖数: 240 | 17 你这样解法不对。你不能保证root2左树中的所有node比root1小。
root2 |
|
P*******b
发帖数: 1001 | 18 来自主题: JobHunting版 - G 家面经 bless!
第一题intersection的函数应该长什么样？
TreeNode* intersection(TreeNode* root1, TreeNode* root2)
返回新的树，这样对吗？
的。 |
|
P*******b
发帖数: 1001 | 19 来自主题: JobHunting版 - G 家面经 bless!
第一题intersection的函数应该长什么样？
TreeNode* intersection(TreeNode* root1, TreeNode* root2)
返回新的树，这样对吗？
的。 |
|
a****a
发帖数: 15 | 20 应该是两个size为m的min-heap（这样能确保min再其中一个heap里面）
heap 1 负责 file 1, heap 2 负责 file 2
每次extract min(root1, root2) 写到 f3, 然后insert new value into the heap
直到file读完 heaps 都为空
至于内存限制.... f3 写的差不多了 就存到disk一下 |
|
c******a
发帖数: 16 | 21 请问在WinEdt里面怎么设啊，我用Texify编译通过了后在弹出来的Yap中不停地报错，
什么invalid argument、Some PostScript specials could not be rendered：
MiKTeX Problem Report
Message: Some PostScript specials could not be rendered.
Data: Error: /undefined in H.S
Operand stack:
--nostringval-- PermitFileReading --nostringval-- PermitFileWriting
--nostringval--
Execution stack:
%interp_exit .runexec2 --nostringval-- --nostringval-- --
nostringval-- 2 %stopped_push --nostringval-- --nostringval-- --
nostr... 阅读全帖 |
|
