已知两颗二叉树,将它们合并成一颗二叉树。合并规则是:都存在的结点,就将结点值加起来,否则空的位置就由另一个树的结点来代替。例如: 两颗二叉树是: 输入:{1,3,2,5},{2,1,3,#,4,#,7} 输出:{3,4,5,5,4,#,7}
时间: 2023-08-19 22:25:26 浏览: 45
题目描述有误,输入的两棵二叉树应该是以层次遍历的方式给出的,例如输入的两棵二叉树应该是:
```
Tree 1: Tree 2:
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
```
按照题目要求,将两棵二叉树合并成一颗二叉树,合并规则是:对应结点相加,如果有一个结点为空,则直接用另一个结点替代。那么合并后的二叉树应该是:
```
3
/ \
4 5
/ \ \
5 4 7
```
下面是一份Python代码实现:
```python
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, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1 and not t2:
return None
elif not t1:
return t2
elif not t2:
return t1
t1.val += t2.val
t1.left = self.mergeTrees(t1.left, t2.left)
t1.right = self.mergeTrees(t1.right, t2.right)
return t1
```
这里使用了递归的方式,对于每个结点,判断是否存在,如果都存在,则将它们的值相加,并递归合并它们的左右子树;如果其中一个为空,则直接返回另一个结点。最终返回合并后的根结点。