まず、二分木のマージの基本的なアイデアを説明します。2つの入力となる二分木を考えます。それぞれの二分木は、ノードと左右の子ノードへのポインタで構成されています。マージ操作では、同じ位置にあるノード同士を統合し、新しいノードを作成します。新しいノードの値は、統合されたノードの値の和や平均など、問題の要件に応じて計算されます。また、子ノードに対して再帰的にマージ操作を行い、新しい二分木を構築します。
以下に、Pythonでの二分木のマージの実装例を示します。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def mergeTrees(t1: TreeNode, t2: TreeNode) -> TreeNode:
if t1 is None:
return t2
if t2 is None:
return t1
merged = TreeNode(t1.val + t2.val)
merged.left = mergeTrees(t1.left, t2.left)
merged.right = mergeTrees(t1.right, t2.right)
return merged
# 二分木の作成
# 例: 二分木1
# 1
# / \
# 3 2
# /
# 5
tree1 = TreeNode(1)
tree1.left = TreeNode(3)
tree1.right = TreeNode(2)
tree1.left.left = TreeNode(5)
# 例: 二分木2
# 2
# / \
# 1 3
# \ \
# 4 7
tree2 = TreeNode(2)
tree2.left = TreeNode(1)
tree2.right = TreeNode(3)
tree2.left.right = TreeNode(4)
tree2.right.right = TreeNode(7)
merged_tree = mergeTrees(tree1, tree2)
# マージ後の二分木を表示
# 期待される出力:
# 3
# / \
# 4 5
# / \ \
# 5 4 7
def printTree(node: TreeNode):
if node is None:
return
print(node.val)
printTree(node.left)
printTree(node.right)
printTree(merged_tree)このコード例では、TreeNodeクラスを使用して二分木を表現し、mergeTrees関数で二分木のマージを行っています。マージされた二分木は再帰的に構築され、最終的なマージ結果を示す新しい二分木が返されます。