二叉树题目：合并二叉树

**合并二叉树**

在计算机科学中，二叉树是一种常见的数据结构，它通过每个结点最多有两个子结点来组织数据。合并二叉树是指将两个二叉树合并成一个新的二叉树，这个新树包含了原来的两颗树中的所有结点。

**定义**

给定两个二叉树 `T1` 和 `T2`，其中 `T1` 的根结点为 `root1`，`T2` 的根结点为 `root2`。我们需要合并这两个二叉树得到一个新的二叉树 `T3`。

**解决方案**

我们可以使用以下步骤来合并这两个二叉树：

1. **创建新结点**:首先，我们需要创建一个新结点作为 `T3` 的根结点。这个新结点的值将是 `root1` 和 `root2` 的最大值。
2. **递归合并子树**:接下来，我们需要递归地合并 `T1` 和 `T2` 的左子树和右子树得到 `T3` 的左子树和右子树。

**代码示例**

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef mergeTrees(root1, root2):
 """
 合并两个二叉树得到一个新的二叉树。
 Args:
 root1 (TreeNode): 第一个二叉树的根结点。
 root2 (TreeNode): 第二个二叉树的根结点。
 Returns:
 TreeNode: 合并后的新二叉树的根结点。
 """
 # 如果两个树都为空，则返回None if not root1 and not root2:
 return None # 如果第一个树不为空，第二个树为空，则返回第一个树 if root1 and not root2:
 return root1 # 如果第一个树为空，第二个树不为空，则返回第二个树 if not root1 and root2:
 return root2 # 创建新结点作为根结点 new_root = TreeNode(root1.val + root2.val)
 # 递归合并左子树和右子树 new_root.left = mergeTrees(root1.left, root2.left)
 new_root.right = mergeTrees(root1.right, root2.right)
 return new_root# 测试代码root1 = TreeNode(1)
root1.left = TreeNode(3)
root1.right = TreeNode(5)

root2 = TreeNode(2)
root2.left = TreeNode(4)
root2.right = TreeNode(6)

new_root = mergeTrees(root1, root2)
print(new_root.val) # 输出:3print(new_root.left.val) # 输出:7print(new_root.right.val) # 输出:11