已知两颗二叉树,将它们合并成一颗二叉树。合并规则是:都存在的结点,就将结点值加起来,否则空的位置就由另一个树的结点来代替。
时间: 2024-03-07 16:50:02 浏览: 3
可以采用递归的方式实现二叉树的合并。具体的合并规则如下:
1. 如果两个二叉树都为空,则返回空。
2. 如果其中一个二叉树为空,则返回另一个二叉树。
3. 如果两个二叉树都不为空,则将它们的根节点的值相加,并创建一个新节点作为合并后的根节点。
4. 递归地对左子树进行合并,将左子树的根节点作为新节点的左子节点。
5. 递归地对右子树进行合并,将右子树的根节点作为新节点的右子节点。
代码实现如下:
```python
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def mergeTrees(t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1 and not t2:
return None
if not t1:
return t2
if not t2:
return t1
root = TreeNode(t1.val + t2.val)
root.left = mergeTrees(t1.left, t2.left)
root.right = mergeTrees(t1.right, t2.right)
return root
```
在这个代码中,我们定义了一个 TreeNode 类来表示二叉树的节点。mergeTrees 函数接收两个二叉树的根节点 t1 和 t2 作为参数,并返回合并后的二叉树的根节点。
在函数的第一行,我们首先判断两个二叉树是否都为空。如果是,则返回空。
接着,我们判断其中一个二叉树是否为空。如果是,则返回另一个二叉树。
最后,如果两个二叉树都不为空,我们创建一个新节点作为合并后的根节点,并将它们的值相加。然后递归地对左子树和右子树进行合并,并将它们分别作为新节点的左子节点和右子节点。最后返回新节点作为合并后的二叉树的根节点。