Leetcode 617. 合并二叉树

心路历程：

看到两颗二叉树的问题，第一反应想到了同频遍历，然后每一步创建新的结点，虽然也写出来了但是代码比较长，而且空间复杂度比较高，好处是没有修改原始的两个二叉树的结果。
后来看了网上的解答，发现可以直接按照修改其中一个二叉树来做，这样代码量会少很多，并且空间复杂度会低，但是这样会导致原来的二叉树被修改。

注意的点：

1、每当调用node.left时都需要保证node不是None
2、当想不明白应该在循环哪一步新建变量时，可以按照循环不变量的角度去思考
3、递归函数return值时，边界return，非边界也要return，是统一的

解法一：同频遍历+创建新的二叉树

# 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: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:

        if not root1 and not root2:
            return None

        new_root = TreeNode()

        # 二叉树同频深度遍历
        def dfs(node1, node2, new_node):
            if not node1 and not node2: return

            if node1 and not node2:
                new_node.val = node1.val
            elif not node1 and node2: 
                new_node.val = node2.val
            else:
                new_node.val = node1.val + node2.val

            if (node1 and node1.left) or (node2 and node2.left):
                new_node_left = TreeNode()
                new_node.left = new_node_left
                if node1 and node2:
                    dfs(node1.left, node2.left, new_node.left)
                elif node1 and not node2:
                    dfs(node1.left, None, new_node.left)
                elif not node1 and node2:
                    dfs(None, node2.left, new_node.left)

            if (node1 and node1.right) or (node2 and node2.right):
                new_node_right = TreeNode()
                new_node.right = new_node_right
                if node1 and node2:
                    dfs(node1.right, node2.right, new_node.right)
                elif node1 and not node2:
                    dfs(node1.right, None, new_node.right)
                elif not node1 and node2:
                    dfs(None, node2.right, new_node.right)
        
        dfs(root1, root2, new_root)
        return new_root

解法二：修改其中一颗二叉树，递归函数直接返回合并后的一个结点

    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node1, node2):  # 将node2结点合并到node1，返回合并后的node1结点
            if not node1: return node2
            if not node2: return node1
            node1.val += node2.val
            node1.left = dfs(node1.left, node2.left)
            node1.right = dfs(node1.right, node2.right)
            return node1
        return dfs(root1, root2)