image.png
递归解法：
# Definition for a binary tree node.
# 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
"""
root = TreeNode()
def merge(node1, node2):
# node = TreeNode()
if not node1 and not node2:
return None
if node1 and node2:
node = TreeNode(node1.val + node2.val)
node.left = merge(node1.left, node2.left)
node.right = merge(node1.right, node2.right)
elif not node1:
node = node2
elif not node2:
node = node1
return node
return merge(root1,root2)
image.png
也可以改成只修改其中一棵树的节点值，而非创建一颗新的二叉树，以节省一点空间。
class Solution(object):
def mergeTrees(self, root1, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: TreeNode
"""
root = TreeNode()
def merge(node1, node2):
# node = TreeNode()
if not node1 and not node2:
return None
if node1 and node2:
node1.val = node1.val + node2.val
node1.left = merge(node1.left, node2.left)
node1.right = merge(node1.right, node2.right)
return node1
elif not node1:
return node2
elif not node2:
return node1
return merge(root1,root2)
image.png
