Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Example 1:
Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
Merged tree:
3
/ \
4 5
/ \ \
5 4 7
Note: The merging process must start from the root nodes of both trees.
Source
# 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
def merge_trees(t1, t2):
"""DFS using a recursion. Writing over t1 + shared nodes
--> it could be a problem if t1 if any of the old trees is deleted
since it's going to also destruct the shared nodes in the new tree
Time Complexity: O(min(|t1|,|t2|))
Space Complexity: O(min(|t1|,|t2|))
"""
if t1 is None:
return t2 # problem if old tree is deleted
if t2 is None:
return t1 # problem if old tree is deleted
t1.val += t2.val
t1.left = merge_trees(t1.left, t2.left)
t1.right = merge_trees(t1.right, t2.right)
return t1 # problem if old tree is deleted
def merge_trees(t1, t2):
"""DFS using a recursion without writing over t1 but still has shared nodes"""
if t1 and t2:
root = TreeNode(t1.val + t2.val)
root.left = merge_trees(t1.left, t2.left)
root.right = merge_trees(t1.right, t2.right)
return root
else:
return t1 or t2 # problem if old tree is deleted
def merge_trees(t1, t2):
"""DFS using a recursion without sharing nodes at all"""
if not t1 and not t2:
return None
if not t1:
node = TreeNode(t2.val)
node.left = merge_trees(None, t2.left)
node.right = merge_trees(None, t2.right)
elif not t2:
node = TreeNode(t1.val)
node.left = merge_trees(t1.left, None)
node.right = merge_trees(t1.right, None)
else:
node = TreeNode((t1.val + t2.val)
node.left = merge_trees(t1.left, t2.left)
node.right = merge_trees(t1.right, t2.right)
return node
def merge_trees(t1, t2):
"""alternative version of above solution with one liners"""
if not t1 and not t2:
return None
node = TreeNode((t1.val if t1 else 0) + (t2.val if t2 else 0))
node.left = merge_trees(t1 and t1.left, t2 and t2.left) # see below for explanation
node.right = merge_trees(t1 and t1.right, t2 and t2.right)
return node
# Here, "x and y" evaluates as follows:
# If x is truthy, the expression evaluates as y. Otherwise, it evaluates as x.
# example:
# None and 5 = None whereas False and 5 = False
# True and 5 = 5
# | t1 = None | t1 != None
# t1 and t1.left = | t1 (= None) | t1.left
Solve it both recursively and iteratively.
from collections import deque
def merge_trees(t1, t2):
"""DFS using an iterative approach. Writing over t1 + shared nodes
Time Complexity O(min(|t1|,|t2|))
Space Complexity O(min(|t1|,|t2|))
"""
if not (t1 and t2):
return t1 or t2
queue1 = deque([t1])
queue2 = deque([t2])
while queue1 and queue2:
node1 = queue1.popleft()
node2 = queue2.popleft()
if node2:
node1.val += node2.val
if (not node1.left) and node2.left:
node1.left = TreeNode(0)
if (not node1.right) and node2.right:
node1.right = TreeNode(0)
queue1.extend([node1.left, node1.right])
queue2.extend([node2.left, node2.right])
return t1
from collections import deque
def merge_trees(t1, t2):
"""DFS using an iterative approach. without writing over t1 or shared nodes."""
if not (t1 and t2):
return t1 or t2
root = TreeNode(0, None, None)
queue1 = deque([t1])
queue2 = deque([t2])
traversal = deque([root])
while queue1 and queue2:
node1 = queue1.popleft()
node2 = queue2.popleft()
ans = traversal.popleft()
if ans:
if not node1 and not node2:
continue
elif not node1:
ans.val = node2.val
queue1.extend([None, None])
queue2.extend([node2.left, node2.right])
left = True if node2.left else False
right = True if node2.right else False
elif not node2:
ans.val = node1.val
queue1.extend([node1.left, node1.right])
queue2.extend([None, None])
left = True if node1.left else False
right = True if node1.right else False
else:
ans.val = node1.val + node2.val
queue1.extend([node1.left, node1.right])
queue2.extend([node2.left, node2.right])
left = True if node1.left or node2.left else False
right = True if node1.right or node2.right else False
ans.left = TreeNode(0, None, None) if left else None
ans.right = TreeNode(0, None, None) if right else None
traversal.extend([ans.left, ans.right])
return root
# Alternatively, we could make a copy of t1 and run the previous algo