2つのバイナリツリーをマージする方法

1. 再帰的なアプローチ: 再帰的なアプローチは、ツリーの各ノードを再帰的にたどりながらマージを行います。以下は、再帰的なアプローチのコード例です。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def mergeTrees(t1, t2):
    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

2. スタックを使用した反復的なアプローチ: スタックを使用して、反復的な方法でツリーのノードを処理することもできます。以下は、スタックを使用した反復的なアプローチのコード例です。

def mergeTrees(t1, t2):
    if t1 is None:
        return t2
    stack = [(t1, t2)]
    while stack:
        node1, node2 = stack.pop()
        if node1 is None or node2 is None:
            continue
        node1.val += node2.val
        if node1.left is None:
            node1.left = node2.left
        else:
            stack.append((node1.left, node2.left))
        if node1.right is None:
            node1.right = node2.right
        else:
            stack.append((node1.right, node2.right))
    return t1

これらの方法を使用すると、2つのバイナリツリーを効率的にマージすることができます。どちらの方法も時間計算量と空間計算量がO(N)であり、Nはツリーのノード数です。適切な方法を選択して、問題に応じたマージを実行してください。