617. 合并二叉树（递归）

617. 合并二叉树

• 题目
• 解题思路
• 代码

题目

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

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

解题思路

创建一颗新树来存放这两棵树叠加后的结果。主要考虑4种情况下的新树节点的值。求出一个节点的值后再用递归框架分别求出这个节点的左子树和右子树的值

代码

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1==null&&t2==null){//t1为空t2为空，新树节点值为null
            return null;
        }
    if (t1 == null) return t2;//t1为空t2不为空，新树节点值为t2.val
    if (t2 == null) return t1;//t1不为空t2为空，新树节点值为t1.val

         TreeNode root=new TreeNode(t1.val+t2.val);//t1不为空t2不为空，新树节点值为t2.val+t1.val
 

       root.left=  mergeTrees(t1.left,t2.left);//递归框架 求出新树的左子树
       root.right=  mergeTrees(t1.right,t2.right);//递归框架 求出新树的右子树
        return root;
    }
}