兼并两个有序数组

给你两个按 非递减次序 摆放的整数数组 nums1 和 nums2，另有两个整数 m 和 n，别离表明 nums1 和 nums2 中的元素数目。

请你 兼并nums2 到 nums1 中，使兼并后的数组相同按 非递减次序 摆放。

**注意：**最终，兼并后数组不应由函数回来，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m n，其间前 m 个元素表明应兼并的元素，后 n 个元素为 0，应忽略。nums2 的长度为 n。

双指针解法

由于两个数组自身是有序的，那么咱们能够界说两个指针，从数组尾部开端遍历，如果nums1[m] > nums2[n]则阐明nums1[m]是最大的，放置在最后，并且移动 m 指针。若小于等于则阐明nums2[n]大，移动nums2[n]至后边排序好数组前。

如此遍历完后得到的就是兼并后的数组。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
      int i = nums1.size() - 1;
      m--;
      n--;
      while(n >= 0) {
        while(m >= 0 && nums1[m] > nums2[n]) {
          swap(nums1[i--], nums1[m--]);
        }
        swap(nums1[i--], nums2[n--]);
      }
    }
};

考虑

“考虑是学习的源泉。”

1. n、m 为何需求先自减 1 ？
2. 示例代码是数组尾部开端遍历，能够改成从数组头开端遍历吗？

兼并后再排序解法

利用库函数直接偷懒，不过在学习算法时最好不要运用库函数，能够自己完成一下排序算法，稳固下十大排序算法。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i=0; i<n; i  ) {
            nums1[m   i] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
    }
};

兼并两个有序链表

将两个升序链表兼并为一个新的 升序 链表并回来。新链表是经过拼接给定的两个链表的一切节点组成的。

双指针解法

这儿采用了兼并两个有序数组的题解思路，思路是一样的。值得注意的是，链表需求界说一个头节点，这样回来新链表的时分能够运用head->next指明。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode(-1);
        ListNode* p = head;
        while(list2 != nullptr) {
            while(list1 != nullptr && list1->val <= list2->val) {
                p->next = list1;
                list1 = list1->next;
                p = p->next;
            }
            p->next = list2;
            list2 = list2->next;
            p = p->next;
        }
        p->next = list1 != nullptr ? list1 : list2;
        return head->next;
    }
};

考虑

1. 去掉 p->next = list1 != nullptr ? list1 : list2; 会怎么？

迭代解法

迭代解法思路更容易理解，即逐个判别list1 或 list2的值大小，然后依照次序将节点拼接成新链表。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode(-1);
        ListNode* p = head;
        while(list1 != nullptr && list2 != nullptr) {
            if(list1->val > list2->val) {
                p->next = list2;
                list2 = list2->next;
            } else {
                p->next = list1;
                list1 = list1->next;
            }
            p = p->next;
        }
        p->next = list1 != nullptr ? list1 : list2;
        return head->next;
    }
};

递归解法

上面迭代的方法，能够分解成子步骤，并能够找到递归出口，list1 或 list2为空的时分。

那么咱们能够这样完成，list1 或 list2为空时，不需求进行兼并，回来另一个链表即可。否则，就需求比较两个链表的元素值，看谁的值更小，由此递归其间一个链表的下一个节点。

递归的最后，即两个链表呈现一个为空的链表，这时分就会结束递归。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr) {
            return list2;
        } else if(list2 == nullptr) {
            return list1;
        } else if(list1->val > list2->val) {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        } else {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
    }
};

兼并二叉树

给你两棵二叉树：root1 和 root2。

幻想一下，当你将其间一棵掩盖到另一棵之上时，两棵树上的一些节点将会堆叠（而另一些不会）。你需求将这两棵树兼并成一棵新二叉树。兼并的规则是：如果两个节点堆叠，那么将这两个节点的值相加作为兼并后节点的新值；否则，不为null 的节点将直接作为新二叉树的节点。

回来兼并后的二叉树。

注意: 兼并进程必须从两个树的根节点开端。

深度优先搜索

咱们能够用递归完成深度优先搜索，递归出口即root1或root2为空的时分，这时分回来另一个树。

当两个节点都不会空时，需求创建一个新节点，元素值即为两个节点元素值之和。然后别离递归两颗树左节点和右节点。

递归的最后，即两个树呈现一个为空，这时分就会结束递归。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
      if(root1 == nullptr) {
        return root2;
      } else if(root2 == nullptr) {
        return root1;
      }
      TreeNode* merged = new TreeNode(root1->val   root2->val);
      merged->left = mergeTrees(root1->left, root2->left);
      merged->right = mergeTrees(root1->right, root2->right);
      return merged;
    }
};