[NC]117. 合并二叉树

🚩传送门：牛客题目
力扣题目

题目

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为NULL的节点将直接作为新二叉树的节点。

合并后的树

解题思路：深度优先搜索

可以使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。

两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。

• 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
• 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
• 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。

对一个节点进行合并之后，还要对该节点的左右子树分别进行合并。这是一个递归的过程。

复杂度分析

时间复杂度：，其中 和 分别是两个二叉树的节点个数。对两个二叉树同时进行深
度优先搜索，只有当两个二叉树中的对应节点都不为空时才会对该节点进行显性合并操作，因此被访
问到的节点数不会超过较小的二叉树的节点数。

空间复杂度：，其中 和 分别是两个二叉树的节点个数。空间复杂度取决于递归调
用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况二叉树的高度等于节点数。

🚩我的代码

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }
}