【C++】二分木で特定のノードのミラー（鏡像）を検索する方法

この問題では、二分木（バイナリツリー）が与えられ、指定されたノードの「ミラー（鏡像）」となるノードを木の中から探します。ここでいうミラーとは、反対側の部分木にある対称の位置に相当するノードのことです。木を中心線で折り返したときに重なり合う位置関係をイメージすると分かりやすいでしょう。

問題例

入力

出力

B のミラーは E

解き方のアプローチ

最もシンプルな解法は、根（ルート）から再帰的に探索を行う方法です。左部分木と右部分木を指す2つのポインタを用意し、両側を同時にたどっていきます。片方のノードが目的の値と一致した時点で、対になる反対側のノードの値を返します。見つからない場合は、さらに深い階層へ再帰呼び出しを続けます。

探索のポイントは、「左の左の子」と「右の右の子」、「左の右の子」と「右の左の子」というように、鏡像の位置関係を保ちながらペアで比較していく点です。これにより、左右非対称な位置にあるノード（ミラーが存在しないノード）も正しく判定できます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int key;
   struct Node* left, *right;
};
struct Node* newNode(int key){
   struct Node* n = (struct Node*) malloc(sizeof(struct Node));
   if (n != NULL){
      n->key = key;
      n->left = NULL;
      n->right = NULL;
      return n;
   }
   else{
      cout << "Memory allocation failed!" << endl;
      exit(1);
   }
}
int mirrorNodeRecur(int node, struct Node* left, struct Node* right){
   if (left == NULL || right == NULL)
      return 0;
   if (left->key == node)
      return right->key;
   if (right->key == node)
      return left->key;
   int mirrorNode = mirrorNodeRecur(node, left->left, right->right);
   if (mirrorNode)
      return mirrorNode;
   return mirrorNodeRecur(node, left->right, right->left);
}
int findMirrorNodeBT(struct Node* root, int node) {
   if (root == NULL)
      return 0;
   if (root->key == node)
      return node;
   return mirrorNodeRecur(node, root->left, root->right);
}
int main() {
   struct Node* root = newNode(1);
   root->left = newNode(2);
   root->left->left = newNode(3);
   root->left->left->left = newNode(4);
   root->left->left->right = newNode(5);
   root->right = newNode(6);
   root->right->left = newNode(7);
   root->right->right = newNode(8);
   int node = root->left->key;
   int mirrorNode = findMirrorNodeBT(root, node);
   cout << "対象ノード: root->left, 値 : " << node << endl;
   if (mirrorNode)
      cout << "ノード " << node << " のミラーは ノード " << mirrorNode << " です";
   else
      cout << "ノード " << node << " のミラーは二分木内に存在しません！";
   node = root->left->left->right->key;
   mirrorNode = findMirrorNodeBT(root, node);
   cout << "\n\n対象ノード: root->left->left->right, 値 : " << node << endl;
   if (mirrorNode)
      cout << "ノード " << node << " のミラーは ノード " << mirrorNode << " です";
   else
      cout << "ノード " << node << " のミラーは二分木内に存在しません！";
   return 0;
}

実行結果

対象ノード: root->left, 値 : 2
ノード 2 のミラーは ノード 6 です

対象ノード: root->left->left->right, 値 : 5
ノード 5 のミラーは二分木内に存在しません！

このように、ノード2（root->left）のミラーは反対側のノード6（root->right）として正しく検出されています。一方、ノード5（root->left->left->right）の対称位置には対応するノードが存在しないため、「ミラーは存在しない」という結果になります。

計算量

このアルゴリズムは木の各ノードを最大1回ずつ訪問するため、ノード数を n とすると時間計算量は O(n) です。また、再帰の深さは木の高さ h に依存するため、空間計算量は O(h) となります。