题解 | #合并二叉树#

方法一（递归）

1.题意整理

• 给定两颗二叉树，将它们合并为一颗二叉树。
• 合并规则是：都存在的节点，就将节点值加起来，否则空的位置就由另一颗树的节点来代替。

2.思路整理

只需利用递归确定合并之后的树的每一个节点值。如果其中一棵树的当前节点为空，直接返回另一颗树的节点。如果均不为空，则将当前的两个节点值相加，并据此新建一个节点，然后递归地确定左子节点和右子节点。

• 递归终止条件：t1为空，返回t2。t2为空，返回t1。
• 递归如何推进：确定好合并二叉树的当前节点之后，要想确定当前节点左子节点，只需往两棵树左子树方向递归。同理，确定右子节点，需要往右子树方向递归。
• 递归的返回值：返回合并二叉树的当前节点。

图解展示：

3.代码实现

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) {
        //t1为空，直接返回t2
        if(t1==null){
            return t2;
        }
        //t2为空，直接返回t1
        if(t2==null){
            return t1;
        }
        //如果两者都不为空，新建一个节点，值为t1的值加上t2的值
        TreeNode node=new TreeNode(t1.val+t2.val);
        //通过递归，确定当前节点的左子节点和右子节点
        node.left=mergeTrees(t1.left,t2.left);
        node.right=mergeTrees(t1.right,t2.right);
        return node;
    }
}

4.复杂度分析

• 时间复杂度：需要遍历两颗树中所有节点，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：最坏情况下，递归栈深度为n，所以空间复杂度是$O(n)O(n)$。