文章目录

• 一【题目类别】
• 二【题目难度】
• 三【题目编号】
• 四【题目描述】
• 五【题目示例】
• 六【解题思路】
• 七【题目提示】
• 八【时间频度】
• 九【代码实现】
• 十【提交结果】

一【题目类别】

• 深度优先搜索

二【题目难度】

• 简单

三【题目编号】

• 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]内两棵树中的节点数目在范围 [0, 2000] 内两棵树中的节点数目在范围[0,2000]内
• −104<=Node.val<=104-10^4 <= Node.val <= 10^4−104<=Node.val<=104

八【时间频度】

• 时间复杂度：O(min(m,n))O(min(m,n))O(min(m,n))，其中m,nm,nm,n分别为传入的两棵二叉树的节点个数
• 空间复杂度：O(min(m,n))O(min(m,n))O(min(m,n))，其中m,nm,nm,n分别为传入的两棵二叉树的节点个数

九【代码实现】

1. Java语言版

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

2. C语言版

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2)
{if(root1 == NULL){return root2;}if(root2 == NULL){return root1;}root1->val = root1->val + root2->val;root1->left = mergeTrees(root1->left,root2->left);root1->right = mergeTrees(root1->right,root2->right);return root1;
}

3. Python语言版

class Solution:def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:if root1 is None:return root2if root2 is None:return root1root1.val = root1.val + root2.valroot1.left = self.mergeTrees(root1.left,root2.left)root1.right = self.mergeTrees(root1.right,root2.right)return root1

4. C++语言版

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 == nullptr){return root2;}if(root2 == nullptr){return root1;}root1->val = root1->val + root2->val;root1->left = mergeTrees(root1->left,root2->left);root1->right = mergeTrees(root1->right,root2->right);return root1;}
};

十【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版
   

4. C++语言版