20天刷题计划-617. 合并二叉树

一、题目描述：

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 输出：[3,4,5,5,4,null,7] 示例 2：

输入：root1 = [1], root2 = [1,2] 输出：[2,2]

提示：

两棵树中的节点数目在范围 [0, 2000] 内 -104 <= Node.val <= 104

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/me…

二、思路分析：

根据题目可以发现, 当树中的某个节点为空时, 这个节点下是不可能存在子节点的.所以同时遍历两个棵树(前序遍历), 每次遍历都需要对节点进行以下判断:

• 当前两个树的节点都为空, 节点下不可能存在子节点，直接返回null.
• 当前两个树存在一个节点为空, 若有则当前节点及其下的子节点合并之后的树是不为空.
• 当两个树的节点都不为空的情况, 需要分别遍历其的左子节点和右子节点.

三、AC 代码：

class Solution {
    public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null&&root2==null) return null;
        if(root1==null&&root2!=null) return root2;
        if(root1!=null&&root2==null) return root1;
        root1.left=mergeTrees(root1.left,root2.left);
        root1.right=mergeTrees(root1.right,root2.right);
        root1.val+=root2.val;
        return root1;
    }
}

四、总结：

对于这种重复的操作，显然离不开循环或递归。在此题便是采用递归的方式解决。

写题解不易，若对你有帮助，点赞评论再走吧。ヽ(✿ﾟ▽ﾟ)ノ，如有不足，请大家斧正。