2222/1337
/README.md
# 1337 - 从一个二叉搜索树到另一个二叉搜索树
题目描述
给定两个二叉搜索树的根节点 root1 和 root2 ，请将 root2 合并到 root1 中。
注意：根节点的值是唯一的，并且节点的值互不相同。
示例 1：
输入：root1 = [2,1,4], root2 = [1,0,3]
输出：[1,0,3,4]
解释：
执行合并操作后，树应如下所示：
节点 1 和节点 2 替换为节点 1（创建一个新节点）。
节点 3 替换为节点 2（创建一个新节点）。
节点 4 没有替换，因为它的值已经是唯一的。
示例 2：
输入：root1 = [1,0,3], root2 = [1,3,4]
输出：[1,0,3,4]
解释：
执行合并操作后，树应如下所示：
节点 0 和节点 1 替换为节点 1（创建一个新节点）。
节点 4 替换为节点 3（创建一个新节点）。
提示：
- 树中的节点数目在范围 [0, 2000] 内
- -1000 <= Node.val <= 1000
- 树中的所有节点的值都是唯一的
- 0 <= Node.val <= 1000
- 题目数据保证 root1 和 root2 都存在。
进阶：
- 如果树的节点数在范围 [0, 100] 内，该如何处理？
- 如果树的节点数在范围 [0, 1000] 内，该如何处理？
- 如果树的节点数在范围 [0, 10000] 内，该如何处理？
思路
题目要求将二叉搜索树 `root2` 合并到二叉搜索树 `root1` 中，使得 `root1` 的节点值由 `root2` 的节点值决定。这实际上等价于将 `root2` 的节点值插入到 `root1` 的对应位置，然后再删除 `root2`，这样 `root1` 就包含了 `root2` 的所有节点值。
我们可以使用递归的方法来实现这个操作。具体步骤如下：
1. 递归遍历 `root1`：
- 如果当前节点在 `root1` 中为空，则返回。
- 如果当前节点在 `root1` 中不为空，则继续递归遍历 `root1` 的左子树和右子树。
- 如果当前节点在 `root1` 中不为空，并且当前节点的值小于 `root2` 的当前节点值，则继续递归遍历 `root1` 的右子树。
- 如果当前节点在 `root1` 中不为空，并且当前节点的值大于等于 `root2` 的当前节点值，则将 `root2` 的当前节点值插入到 `root1` 的当前节点值之前。
2. 递归遍历 `root2`：
- 如果当前节点在 `root2` 中为空，则返回。
- 将 `root2` 的当前节点值插入到 `root1` 的当前节点值之前。
- 递归遍历 `root2` 的左子树和右子树。
通过这种方法，我们可以确保 `root1` 中包含了 `root2` 中的所有节点值，并且 `root1` 的节点值保持有序。
复杂度分析
- 时间复杂度： O(m + n)，其中 m 和 n 分别是 `root1` 和 `root2` 的节点数。在最坏情况下，我们需要遍历所有的节点。
- 空间复杂度： O(m + n)，递归调用栈的空间取决于树的高度，最坏情况下为 O(m + n)。
```python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
if not root1:
return root2
if not root2:
return root1
if root1.val < root2.val:
root1.left = self.mergeTrees(root1.left, root2)
root1.right = self.mergeTrees(root1.right, root2.right)
else:
root2.left = self.mergeTrees(None, root1.left)
root2.right = self.mergeTrees(None, root1.right)
root1 = root2
root1.left =