题解 | #合并二叉树#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    //需要同时遍历两棵树,都用先序遍历,直接合并到t1上，空间复杂度为O(1)
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1==nullptr&&t2==nullptr) 
            return nullptr; 
        if(t1==nullptr)
            return t2;   //返回不为空的结点
        if(t2==nullptr)
            return t1;     
        //如果两个结点都不为空，则将值加起来
        t1->val = t1->val + t2->val; 
        t1->left = mergeTrees(t1->left,t2->left);  //合并左子树
        t1->right = mergeTrees(t1->right,t2->right);//合并右子树
        //遍历完该结点的左子树和右子树后，在将当前结点处理的结果返回
        return t1;
    }
};

解题思路：为了能够减少空间开销，实现空间复杂度为O(1),这里就直接将t2合并到t1上面去。合并两棵二叉树，可以分解为合并这两棵二叉树对应的左子树和右子树，也就是将问题化解成多个子问题，每个子问题要解决的事情是一样的。因此利用到递归来处理这种思想，递归适用于处理原问题相似的规模较小的问题，将原问题化解为规模更小的问题，直到子问题方便处理。

那么什么时候该问题才能方便处理呢，如果子问题变成了合并两个结点，那处理起来就方便多了，合并结点有以下3种情况。

1. 两个结点都为空,那么返回空
2. 两个结点其中一个为空，那么我们让第一个结点等于不为空的结点（合并到第一个结点）
3. 两个结点都不为空，那么将两个结点的值加起来，并赋值给第一个结点。

综上所述，原问题可以利用递归不断划分为合并当前结点的左右子树，全部合并到第一棵子树，同时遍历这个两棵子树的左子树和右子树，那么1号二叉树根结点的左儿子就是合并其左儿子结点和2号二叉树左儿子结点的过程。合并右子树同理。不断的递归，当走到了两个结点之间的合并时，即走到了递归终止的条件，这个时候按照上述3种情况的合并规则来合并即可。