亚麻社招onsite

仅供参考：
void recursionMerge(TreeNode root1, TreeNode root2)
//根为root1的树接收节点， 根为root2的树被遍历，挨个插入root1的那棵树
        if root2 is null, return
        TreeNode tempLeft = root2.left; TreeNode tempRight = root2.right;
        root2.left = null; root2.right = null;
        insert(root1, root2);        // 调用另外一个函数，insert a single TreeNode to BST
        recursionMerge(root1, tempLeft);
        recursionMerge(root1, tempRight);
还可以多写一个wrapper函数来快速解决，root1为空或者root2为空的情况
递归函数产生的额外空间无所谓，当然和面试官确认下是最稳的

字母比较低调 发表于 2018-2-15 14:40
否则被拆散的节点会继续连在在以前的左右子节点上

xiexie : )

Thanks to LZ. I used bottom-up recursion to save temporary pointers.

1. void insertBST(Node* r, Node* x) {
   
2.     if (!r || !x) return;
   
3.     if (x->val < r->val)
   
4.         if (r->left) r = r->left;
   
5.         else insertBST(r->left, x);
   
6.     else if (r->right) r = r->right;
   
7.     else insertBST(r->right, x);
   
8. }
   
9. 
   
10. void mergeBST(Node* r1, Node* r2) {
    
11.     if (!r2) return;
    
12.     mergeBST(r1, r2->left), mergeBST(r1, r2->right);
    
13.     r2->left = r2->right = nullptr;
    
14.     insertBST(r1, r2);
    
15. }

复制代码