这种解法对吗？merge two BST# JobHunting - 待字闺中
w*o
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;
}
这样的解法是不对？不快？还是有其它不好？
么啰嗦？
不能这样直接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;
}
这样的解法是不对？不快？还是有其它不好？
