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(root1, left);
} else {
//..........
}
return root1;
}
这样的解法是不对？不快？还是有其它不好？ |
l***m
发帖数: 339 | 2 我会你这么解，肯定不会merge两个array。
root2
【在 w***o 的大作中提到】
: 看到很多解法都是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)
|
h*****n
发帖数: 188 | 3 wrong.
try a few sample cases.
root2
【在 w***o 的大作中提到】
: 看到很多解法都是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)
|
l*****r
发帖数: 393 | 4 Wrong, check the BST definition again.
root2
【在 w***o 的大作中提到】
: 看到很多解法都是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)
|
w****x
发帖数: 2483 | |
y*****n
发帖数: 243 | |
p*****2
发帖数: 21240 | 7
太膜拜了。150行code。
【在 w****x 的大作中提到】
: 转换成linked list再merge
: http://haixiaoyang.wordpress.com/?s=merge+bst
|
d**e
发帖数: 6098 | 8 post order遍历tree2，逐个逐个insert到tree1也可行吧。
root2
【在 w***o 的大作中提到】
: 看到很多解法都是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)
|
g****y
发帖数: 240 | 9 你这样解法不对。你不能保证root2左树中的所有node比root1小。
root2
【在 w***o 的大作中提到】
: 看到很多解法都是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)
|
w***o
发帖数: 109 | 10 当然没有假定root2左树中的所有node比root1小.
所以我才用
root1 = mergeBST(root1, left);
而不是：
root1.left = mergeBST(root1.left, left);
【在 g****y 的大作中提到】
: 你这样解法不对。你不能保证root2左树中的所有node比root1小。
:
: root2
|
w***o
发帖数: 109 | 11 我要是面试时候白板写这么多code，肯定无数bug.
【在 w****x 的大作中提到】
: 转换成linked list再merge
: http://haixiaoyang.wordpress.com/?s=merge+bst
|
n******n
发帖数: 567 | 12 LZ, 我觉得这么修改一些就对了。
void fun(Node roota, Node rootb){
Node x = findRootaInTreeB(roota, rootb);// O(lgn) time
rotateTreeB(rootB,x);//rotate x as the new root of tree B // O(1) time
//continue your algorithm.....
}
时间还是O(n) |
H****s
发帖数: 247 | 13 这样可以，只是不保证merge后的树balance. 而且时间是O(nlogn)
【在 d**e 的大作中提到】
: post order遍历tree2，逐个逐个insert到tree1也可行吧。
:
: root2
|
