题解 | #合并二叉树#

题目描述
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：
两颗二叉树是:
Tree 1
1
/ \
3 2
/
5

Tree 2
2
/
1 3
\
4 7

合并后的树为
3
/
4 5
/ \
5 4 7

方法一：队列的思想

求解思路
对于本题要合并二叉树，我们可以借用一个队列，利用队列将两个二叉树根节点存储，然后队列弹出根节点相加，接着如果两个树的左节点均不为空，则将其放入队列，相应的如果右子树的结点均不为空，则同样操作。最后我们不断将子树放入队列，再从队列中取出节点，直到队列为空，这样最终即可得到合并后的二叉树。

图片说明

解题代码

import java.util.*;
public class Solution {
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if(t1==null || t2==null)//存在一个二叉树为空，则返回另一个二叉树
        {
            return t1==null? t2 : t1;
        }
        LinkedList<TreeNode> mylinkedList = new LinkedList<>(); // 声明一个队列存储二叉树
        mylinkedList.add(t1);
        mylinkedList.add(t2);
        while (!mylinkedList.isEmpty())
        {
            TreeNode n1 = mylinkedList.poll(); // 弹出一个元素
            TreeNode n2 = mylinkedList.poll();
            n1.val = n1.val + n2.val;
            if (n1.left != null && n2.left != null) // 两个数的左子树都不为空则将其放到列表中
            {
                mylinkedList.add(n1.left); // 添加子树
                mylinkedList.add(n2.left);
            }
            else if (n1.left == null) // 如果t1的左子树为空，将t2的左子树直接赋予t1
            {
                n1.left = n2.left; // 将n2的左子树赋值给n1
            }
            if (n1.right != null && n2.right != null) // 两个数的右子树都不为空则将其放到列表中
            {
                mylinkedList.add(n1.right); // 同上面的思路
                mylinkedList.add(n2.right);
            }
            else if (n1.right == null) // 如果t1的右子树为空，将t2的右子树直接赋予t1
            {
                n1.right = n2.right;
            }
        }
        return t1; // 返回最终的二叉树
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用队列，引入了额外的内存地址空间，因此空间复杂度为 $O(N)$

方法二：优化方法--递归的思想

求解思路
我们对第一种方法进行优化，使用先序遍历的方法对二叉树进行遍历，在遍历的过程中对两个二叉树的相应节点进行相加。如果一个树的节点为空，另一个树的节点不为空，则将另一个树节点的值赋给第一个树。按上面的描述进行递归，最终求得合并之后的二叉树。

图片说明

解题代码

import java.util.*;
public class Solution {
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) 
    {   //递归方法，简洁明了！
        if(t1 != null && t2 !=null) // 递归中止的条件，树t1节点为空并且树t2的节点为空
        {
            t1.val += t2.val; // 将两个树的结点数值相加
            t1.left = mergeTrees(t1.left, t2.left); // 递归合并两个树的左节点
            t1.right = mergeTrees(t1.right, t2.right); // 递归合并两个数的右节点
        }
        return t1 == null? t2 : t1; // 递归终止条件
    }
}

复杂度分析
时间复杂度：其时间取决于递归的层数，和树的深度有关，因此时间复杂度为 $O(N)$ ，其中N为两棵树结点数的较小值。
空间复杂度：没有引入新的内存地址空间，因此空间复杂度为 $O(1)$