617.合并二叉树
- 题目:
1 | 给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。 |
- 思路:
两棵二叉树合并,最简单的思路就是两棵树同时做相同的遍历,就像遍历单棵树一样,不过判断条件是两棵树相同位置的节点。
递归代码如下:
1 | /** |
但是执行用时和内存消耗都很严重。分析:
由于两棵树需要都遍历一遍(除去不是两侧节点都不为空的情况),因此时间复杂度
O(M+N)
(空指针的情况不访问节点,只修改指针);空间复杂度由于是直接修改t1
,因此也是O(N)
。
递归:
由于需要比较每两个对应的节点,那么参考对称二叉树的思路,将每个节点的指针保存起来,两棵树对应的节点相邻放置,每次判断两个节点。需要注意的树如果节点为空,要保存空节点,必须要占位;其次,为了改变t1
所在的树,需要在必要时新建节点。在迭代开始时首先处理根节点,其次对左树和右树的左右节点进行判断,进行相应新建。
这样的思路,空间复杂度首先为O(M+N)
,时间复杂度一样为O(M+N)
。
代码如下:
1 | /** |
Note:这中间出错的点:需要在当前步骤新建左右节点,指针才有效,否则空节点入队已经是一个空节点的拷贝,对其进行赋值是无效的。