本記事では、特定のアルゴリズム問題に対するアプローチと実装について考察します。ユニオンファインド、ハッシュテーブル、そして二分木のさまざまな操作（巡回、比較、対称性チェック、パス計算）に焦点を当てます。

アカウントのマージ問題

複数のメールアドレスが同一人物に属するかを判断し、関連するすべてのアドレスを統合する問題について考えます。これは、互いに接続された要素のグループを効率的に管理する「ユニオンファインド（Disjoint Set Union, DSU）」データ構造と、文字列（メールアドレス）と数値IDをマッピングするためのハッシュテーブルを組み合わせることで解決できます。

まず、各メールアドレスにユニークな整数IDを割り当てるハッシュマップと、そのIDから元の所有者名を参照するための別のハッシュマップを準備します。アカウント情報が与えられたら、各アカウント内のすべてのメールアドレスを同じグループに統合します。これは、ユニオンファインドの「union」操作を使用して行います。具体的には、アカウント内の最初のメールアドレスを代表者として、残りのすべてのアドレスをその代表者のグループに統合します。

すべての統合操作が完了した後、各代表者IDに属するすべてのメールアドレスを収集します。問題の要件に従い、最終的な出力は各グループ内のメールアドレスをASCII順でソートする必要があります。

二つの同一なツリーの判定

二つの二分木が構造的にも値も同一であるかを判定する問題です。この種の比較には、深さ優先探索（DFS）を用いた再帰的なアプローチが非常に効果的です。

比較関数では、まず以下の基本ケースを考慮します。

• 両方のノードがnullptrであれば、同一と見なしtrueを返します。
• いずれか一方のノードがnullptrであれば、同一ではないと見なしfalseを返します。
• 両方のノードが存在するが、それらの値が異なる場合は、同一ではないと見なしfalseを返します。

上記のいずれにも該当しない場合、つまり両ノードが存在し、その値も同じであれば、再帰的に左右の子ノードを比較します。左の子ノード同士の比較結果と、右の子ノード同士の比較結果が両方ともtrueである場合にのみ、全体として同一であると判断します。

class Solution {
public:
    // 二つの二分木が同一であるかを判定する関数
    bool checkIdenticalTrees(TreeNode* tree1, TreeNode* tree2) {
        // 基本ケース：両方ともnullなら同一
        if (tree1 == nullptr && tree2 == nullptr) {
            return true;
        }
        // 基本ケース：どちらか一方がnullなら同一ではない
        if (tree1 == nullptr || tree2 == nullptr) {
            return false;
        }
        // 基本ケース：値が異なるなら同一ではない
        if (tree1->val != tree2->val) {
            return false;
        }
        // 再帰ステップ：左部分木同士、右部分木同士を比較
        return checkIdenticalTrees(tree1->left, tree2->left) && checkIdenticalTrees(tree1->right, tree2->right);
    }
};

対称な二分木の判定

与えられた二分木が、その中央を軸として左右対称（ミラーイメージ）であるかを判定する問題です。これも再帰的なアプローチで効率的に解決できます。

ここでは、二つのノードを受け取り、それらが互いにミラーイメージであるかをチェックするヘルパー関数を定義します。このヘルパー関数isMirrorは次のように動作します。

• 両方のノードがnullptrであれば、ミラーであると見なしtrueを返します。
• いずれか一方のノードがnullptrであれば、ミラーではないと見なしfalseを返します。
• 両方のノードが存在するが、それらの値が異なる場合は、ミラーではないと見なしfalseを返します。

上記の条件に合致しない場合、つまり両ノードが存在し、その値も同じであれば、再帰的に「ノード1の左の子とノード2の右の子」がミラーであるか、そして「ノード1の右の子とノード2の左の子」がミラーであるかをチェックします。これら両方がtrueであれば、全体として対称であると判断します。主関数からは、ルートノードの左右の子ノードをこのヘルパー関数に渡して呼び出します。

class Solution {
public:
    // 二つのノードが互いにミラーであるかを判定するヘルパー関数
    bool isMirror(TreeNode* nodeA, TreeNode* nodeB) {
        // 両方nullならミラー
        if (nodeA == nullptr && nodeB == nullptr) {
            return true;
        }
        // 片方だけnullならミラーではない
        if (nodeA == nullptr || nodeB == nullptr) {
            return false;
        }
        // 値が異なるならミラーではない
        if (nodeA->val != nodeB->val) {
            return false;
        }
        // 再帰ステップ：nodeAの左とnodeBの右、nodeAの右とnodeBの左を比較
        return isMirror(nodeA->left, nodeB->right) && isMirror(nodeA->right, nodeB->left);
    }

    // ツリー全体が対称であるかを判定する関数
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) { // ルートがnullなら対称
            return true;
        }
        return isMirror(root->left, root->right);
    }
};

パスの合計値判定

二分木のルートから葉までのパスの中で、特定の目標値と等しくなる合計値を持つパスが存在するかを判定する問題です。この問題も深さ優先探索（DFS）をベースとした再帰によって解くことができます。

再帰関数では、現在のノードと残り目標値（targetSumから現在のノードの値を引いたもの）を受け取ります。以下の条件でパスを評価します。

• 現在のノードがnullptrであれば、そのパスは無効であるためfalseを返します。
• 現在のノードが葉（リーフ）ノード、つまり左右の子ノードが両方ともnullptrである場合、現在のノードの値が残り目標値と等しいかどうかを確認します。等しければtrue、そうでなければfalseを返します。

上記のいずれにも該当しない場合、つまり現在のノードが内部ノードである場合は、左右の子ノードに対して再帰的に同じ処理を適用します。この際、次のノードに渡す残り目標値は、現在のノードの値だけ減算されたものになります。左の子ノードへのパス、または右の子ノードへのパスのどちらか一方が成功すれば、全体のパスが存在すると判断するため、論理和（||）を使用します。

class Solution {
public:
    // 指定された合計値を持つパスがツリー内に存在するかを判定
    bool checkPathSum(TreeNode* currentNode, int remainingSum) {
        // ベースケース1: 現在のノードがnullの場合、パスは存在しない
        if (currentNode == nullptr) {
            return false;
        }

        // ベースケース2: リーフノードの場合、現在のノードの値が残り合計値と一致するか確認
        if (currentNode->left == nullptr && currentNode->right == nullptr) {
            return currentNode->val == remainingSum;
        }

        // 再帰ステップ: 左の子または右の子を探索
        // 現在のノードの値を残り合計値から減算して再帰呼び出し
        bool leftPath = checkPathSum(currentNode->left, remainingSum - currentNode->val);
        bool rightPath = checkPathSum(currentNode->right, remainingSum - currentNode->val);

        // どちらか一方でも成功すればtrue
        return leftPath || rightPath;
    }

    // パス合計値のメイン関数
    bool hasPathSum(TreeNode* root, int targetSum) {
        return checkPathSum(root, targetSum);
    }
};