[数据结构与算法]深度优先搜索和广度优先搜索

617.合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

思路： 每次要存两个树节点的元祖共同遍历，直接在左树上进行操作，在循环中先将左树加上右树值，再对两个节点的左右子树判定，都为非空则入队列，否则直接赋值左树的左右子树为另一非空值。
bfs：

# Definition for a binary tree node.
# 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, root1: TreeNode, root2: TreeNode) -> TreeNode:
        q = collections.deque()
        if not root1 or not root2:
            return root1 if root1 else root2
        q.append((root1, root2))
        while q:
            r1, r2 = q.popleft()
            r1.val += r2.val
            if r1.left and r2.left:
                q.append((r1.left, r2.left))
            elif not r1.left:
                r1.left = r2.left
            if r1.right and r2.right:
                q.append((r1.right, r2.right))
            elif not r1.right:
                r1.right = r2.right
        return root1

dfs：
思路： 在左树上操作，dfs返回树节点，每次先判断是否都为空，有空直接返回，否则左树加上右树，左树左子树和右子树分别递归，最后返回左子树

# Definition for a binary tree node.
# 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, root1: TreeNode, root2: TreeNode) -> TreeNode:
        def dfs(l, r):
            if not l or not r:
                return l if l else r 
            l.val += r.val
            l.left = dfs(l.left, r.left)
            l.right = dfs(l.right, r.right)
            return l
        return dfs(root1, root2)