LeetCode: 617 Merge Two Binary Trees

You are given two binary trees root1 and root2.
Imagine that when you put one tree over the other, some nodes of the two trees overlap while others do not. You need to merge the two trees into a new binary tree.
The merge rule is that if two nodes overlap, then sum the values of the two nodes. Otherwise, the non-null node will be used as the node of the new tree.

Example

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
Explanation: 
- The merged tree is formed by adding the overlapping nodes and copying the non-overlapping nodes.

问题

给定两棵二叉树 root1 和 root2。
设想你将其中一棵树放在另一棵树上，其中一些节点会重叠，而另一些不会。你需要将两棵树合并为一棵新二叉树。
合并规则是：如果两个节点重叠，则将两个节点的值相加。否则，将非空节点用作新树的节点。

例子

输入: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出: [3,4,5,5,4,null,7]
解释: 
- 合并后的树是通过相加重叠节点和复制未重叠节点形成的。

Solution

Approach: Depth-First Search (DFS) / 深度优先搜索

To merge two binary trees, we can use Depth-First Search (DFS) recursively. At each step, if both trees have a node, we sum their values. If only one of the trees has a node, we use that node directly.

Approach Explanation / 方法解释

1. Base Case: If one of the trees is None, return the other tree.
2. Recursive Merge: At each node, sum the values of the nodes from root1 and root2. Recursively merge the left and right children of both trees.
3. Return Merged Node: Once merged, return the new node, which contains the sum of values (or the non-null node).

Algorithm / 算法

1. If root1 is None, return root2.
2. If root2 is None, return root1.
3. Sum the values of root1 and root2 for the current node.
4. Recursively merge the left and right children.
5. Return the merged tree.

Implementation / 实现

Python

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1:
            return root2
        if not root2:
            return root1

        # Merge the values of the two nodes
        merged_root = TreeNode(root1.val + root2.val)

        # Recursively merge the left and right children
        merged_root.left = self.mergeTrees(root1.left, root2.left)
        merged_root.right = self.mergeTrees(root1.right, root2.right)

        return merged_root

Explanation / 解释

1. Base Case: If One Tree is None / 基本情况：如果一棵树为 None

   if not root1:
      return root2
   if not root2:
      return root1

   • English: If either root1 or root2 is None, return the other tree because it will represent the merged tree.
   • Chinese: 如果 root1 或 root2 为空，返回另一棵树，因为它将代表合并后的树。

2. Merge Node Values / 合并节点值

   merged_root = TreeNode(root1.val + root2.val)

   • English: Create a new node with the sum of the values from root1 and root2.
   • Chinese: 创建一个新节点，其值为 root1 和 root2 的值之和。

3. Recursively Merge Children / 递归合并子节点

   merged_root.left = self.mergeTrees(root1.left, root2.left)
   merged_root.right = self.mergeTrees(root1.right, root2.right)

   • English: Recursively merge the left and right children of both trees.
   • Chinese: 递归合并两棵树的左右子节点。

4. Return the Merged Tree / 返回合并后的树

   return merged_root

   • English: Return the newly created merged tree node.
   • Chinese: 返回新创建的合并树节点。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n), where n is the number of nodes in the smaller tree. We visit each node in both trees once.
• Space Complexity / 空间复杂度: O(h), where h is the height of the tree, representing the recursion stack depth.

Key Concept / 关键概念

• Recursion / 递归: This problem is naturally recursive, as each tree can be thought of as consisting of smaller subtrees. We merge these subtrees recursively.
• Node Merging / 节点合并: When merging two nodes, sum their values and recursively merge their children.

Summary / 总结

• English: The problem of merging two binary trees can be efficiently solved using DFS, where we sum the values of overlapping nodes and recurse on their children.
• Chinese: 合并两棵二叉树的问题可以通过使用深度优先搜索 (DFS) 高效解决，其中我们将重叠节点的值相加，并递归处理它们的子节点。

Tips / 提示

• English: Practice problems involving binary tree recursion to better understand how to handle tree traversal and node merging.
• Chinese: 练习涉及二叉树递归的问题，以更好地理解如何处理树的遍历和节点合并。

5 More Similar Questions / 推荐5问题

1. LeetCode 226. Invert Binary Tree
2. LeetCode 112. Path Sum
3. LeetCode 572. Subtree of Another Tree
4. LeetCode 100. Same Tree
5. LeetCode 108. Convert Sorted Array to Binary Search Tree

Recommended Resources / 推荐资源

• English: Practice binary tree recursion problems to improve your understanding of tree manipulation.
• Chinese: 练习二叉树递归问题，以提高对树操作的理解。