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 = val
        self.left = left
        self.right = right
class Solution(object):
    def mergeTrees(self, root1, root2): # 传入参数 就是两棵树 这里以根节点表示
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: TreeNode
        """
        # 遍历两棵树 与遍历一棵树的逻辑是一样的 这里采用前序遍历的方式
        if not root1:
            return root2
        if 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 root2
        if not root2:
            return root1
        queue = 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.val
            if not node1.left and node2.left: # node1无左节点 那就用node2的 node2没用也没事 就是Null
                node1.left = node2.left
            if not node1.right and node2.right:
                node1.right = node2.right
        
        return root1