力扣刷题-二叉树-合并二叉树

617.合并二叉树（经典）

合并二叉树是操作两棵树的题目里面很经典的，如何对两棵树遍历以及处理？
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:

注意: 合并必须从两个树的根节点开始。

思路

参考：https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html
如何同时遍历两个二叉树呢？
其实和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作。

递归

二叉树使用递归，就要想使用前中后哪种遍历方式？
本题使用哪种遍历都是可以的！
我们下面以前序遍历为例。

1. 确定递归函数的参数和返回值：

首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。

2. 因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了（如果t2也为NULL也无所谓，合并之后就是NULL）。

反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。

3. 确定单层递归的逻辑：

单层递归的逻辑就比较好写了，这里我们重复利用一下t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构）。
那么单层递归中，就要把两棵树的元素加到一起。
接下来t1 的左子树是：合并 t1左子树 t2左子树之后的左子树。
t1 的右子树：是 合并 t1右子树 t2右子树之后的右子树。
最终t1就是合并之后的根节点。

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution(object):def mergeTrees(self, root1, root2): # 传入参数 就是两棵树 这里以根节点表示""":type root1: TreeNode:type root2: TreeNode:rtype: TreeNode"""# 遍历两棵树 与遍历一棵树的逻辑是一样的 这里采用前序遍历的方式if not root1:return root2if not root2:return root1# 中 中的处理逻辑就是节点的值相加root1.val += root2.val # 根节点更新(以root1表示更新之后的树)# 左root1.left = self.mergeTrees(root1.left, root2.left)# 右root1.right = self.mergeTrees(root1.right, root2.right)return root1# 当然 也可以新建节点 比如 root

迭代法

# 法二 迭代法 需要模拟队列来存储两棵树上的节点 这样就是层序遍历
from collections import deque
class Solution(object):def mergeTrees(self, root1, root2):if not root1:return root2if not root2:return root1queue = deque()queue.append(root1)queue.append(root2)while queue: # 以root1为更新之后的树# 弹出节点node1 = queue.popleft()node2 = queue.popleft()# 左if node1.left and node2.left: # 两边左节点都存在queue.append(node1.left)queue.append(node2.left)# 右if node1.right and node2.right: # 两边右节点都存在queue.append(node1.right)queue.append(node2.right)# 更新当前节点. 同时改变当前节点的左右孩子. node1.val += node2.valif not node1.left and node2.left: # node1无左节点 那就用node2的 node2没用也没事 就是Nullnode1.left = node2.leftif not node1.right and node2.right:node1.right = node2.rightreturn root1