Recursively traverse both trees simultaneously. If both nodes exist, sum their values and recurse on left and right children. If only one node exists, return that node. If neither exists, return None.
Use a queue to traverse both trees level by level. At each step, merge overlapping nodes by summing their values. If a child exists in only one tree, attach it directly.
""" 0617.1 - Merge Two Binary Trees - Solution 1 - Recursive DFS """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
"""Merge Two Binary Trees Function"""
if not root1 and not root2:
return None
if not root1:
return root2
if not root2:
return root1
merged = TreeNode(root1.val + root2.val)
merged.left = self.mergeTrees(root1.left, root2.left)
merged.right = self.mergeTrees(root1.right, root2.right)
return merged
#####################################################################################
# Functions
#####################################################################################
def build_tree(values):
"""Build a binary tree from a list of values (level-order)"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
def tree_to_list(root):
"""Convert binary tree to level-order list"""
if not root:
return []
result = []
queue = [root]
while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
def testcase():
"""Test Function"""
root1 = build_tree([1, 3, 2, 5])
root2 = build_tree([2, 1, 3, None, 4, None, 7])
print(tree_to_list(Solution().mergeTrees(root1, root2)))
# Expected: [3, 4, 5, 5, 4, None, 7]
root1 = build_tree([1])
root2 = build_tree([2])
print(tree_to_list(Solution().mergeTrees(root1, root2)))
# Expected: [3]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0617.2 - Merge Two Binary Trees - Solution 2 - Iterative BFS """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
from collections import deque
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
"""Merge Two Binary Trees Function"""
if not root1:
return root2
if not root2:
return root1
queue = deque([(root1, root2)])
while queue:
node1, node2 = queue.popleft()
node1.val += node2.val
if node1.left and node2.left:
queue.append((node1.left, node2.left))
elif not node1.left:
node1.left = node2.left
if node1.right and node2.right:
queue.append((node1.right, node2.right))
elif not node1.right:
node1.right = node2.right
return root1
#####################################################################################
# Functions
#####################################################################################
def build_tree(values):
"""Build a binary tree from a list of values (level-order)"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
def tree_to_list(root):
"""Convert binary tree to level-order list"""
if not root:
return []
result = []
queue = [root]
while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
def testcase():
"""Test Function"""
root1 = build_tree([1, 3, 2, 5])
root2 = build_tree([2, 1, 3, None, 4, None, 7])
print(tree_to_list(Solution().mergeTrees(root1, root2)))
# Expected: [3, 4, 5, 5, 4, None, 7]
root1 = build_tree([1])
root2 = build_tree([2])
print(tree_to_list(Solution().mergeTrees(root1, root2)))
# Expected: [3]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()