题解 | #合并二叉树#

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

5  4    7

示例1

输入：{1,3,2,5},{2,1,3,#,4,#,7}

返回值：{3,4,5,5,4,#,7}

对二叉树的遍历还可通过层序遍历，即在层序遍历的过程中合并二叉树，此时需要使用一个辅助的数据结构，此处使用了队列，首先利用队列将两个二叉树根节点存储，然后队列弹出根节点相加，如果两个树的左节点均不为空，增将其放入队列，相应的如果两个树的右节点均不为空，增将其放入队列中，如果t1二叉树的左节点为空,t2左节点不为空，直接将t2的左节点赋予t1，同理右节点也如此，由此我们不断将子树放入队列，再从队列中取出节点，直到队列为空。层序遍历的核心思想是一层一层进行遍历。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if(t1==null || t2==null)//存在一个二叉树为空，则返回另一个二叉树
        {
            return t1==null? t2 : t1;
        }
        LinkedList<TreeNode> linkedList = new LinkedList<>();//声明一个队列用于存储二叉树
        linkedList.add(t1);
        linkedList.add(t2);
        while (!linkedList.isEmpty()){
            TreeNode n1 = linkedList.poll();//弹出一个元素。根据不同的数据结构，结果也相应不同，此处为二叉树
            TreeNode n2 = linkedList.poll();
            n1.val = n1.val + n2.val;
            if (n1.left != null && n2.left != null)//两个数的左子树都不为空则将其放到列表中
            {
                linkedList.add(n1.left);
                linkedList.add(n2.left);
            }
            else if (n1.left == null)//如果t1的左子树为空，将t2的左子树直接赋予t1
            {
                n1.left = n2.left;
            }
            if (n1.right != null && n2.right != null)//两个数的右子树都不为空则将其放到列表中
            {
                linkedList.add(n1.right);
                linkedList.add(n2.right);
            }
            else if (n1.right == null)////如果t1的右子树为空，将t2的右子树直接赋予t1
            {
                n1.right = n2.right;
            }
        }
        return t1;
    }
}

复杂度分析

• 时间复杂度：层序遍历时间复杂度为$O(N)$
• 空间复杂度：借助了一个辅助队列来存储二叉树节点，因此空间复杂度为$O(N)$

我们已经知道对二叉树的访问有前序、中序、后序遍历三种基本的办法，那么我们可以想到可以使用前序遍历的方法对二叉树进行遍历，在遍历的过程中对两个二叉树的相应节点进行相加，这个过程可以用到递归方法，即树t1节点并且树t2的节点不为空时，合并两个节点的数值，递归合并两个树的左节点，递归合并两个树的右节点，如果树t1节点或者树t2的节点为空时，将树t2的节点赋值给t1,当两个数的节点都为空时，遍历完成，递归也就完成，此时t1即为合并后的二叉树。

先进行根节点的合并，然后对左子树进行递归合并，之后对右子树递归合并，当两个树的节点均为空时，递归条件结束

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        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(min(t1,t2))$
• 空间复杂度：取决于递归调用的层数，递归调用的层数不会大于最小二叉树的高度，即空间复杂度$O(min(h1,h2))$，其中h1,h2分别为二叉树t1,t2的高度,最坏情况下二叉树的高度等于节点数