C++でクローンされた二分木から対応するノードを検索する方法

問題概要

2つの二分木「original（元の木）」と「cloned（クローン木）」が与えられ、さらに元の木に存在する特定のノード target への参照が渡されます。クローン木は元の木とまったく同じ構造を持つコピーです。ここでの課題は、クローン木の中から target に対応する同じ位置のノードへの参照を見つけ出すことです。

例えば、下図のような木が与えられ、target の値が 3 である場合、出力は 3 となります。

解決のアプローチ

この問題は、元の木とクローン木を同時に再帰的にたどることで解けます。両方の木は構造が完全に一致しているため、元の木の走査中に target を発見した時点で、クローン木の同じ位置にあるノードを返せばよいのです。具体的な手順は以下の通りです。

• solve() というメソッドを定義します。このメソッドは node1、node2、target を引数として受け取ります
• node1 が NULL の場合は NULL を返します
• node1 が target と同一であり、かつ node1 の値が node2 の値と等しい場合、node2 を返します
• leftPart := solve(node1 の左の子、node2 の左の子、target) として左側の部分木を探索します
• rightPart := solve(node1 の右の子、node2 の右の子、target) として右側の部分木を探索します
• leftPart が NULL でなければ leftPart を返し、そうでなければ rightPart を返します
• メイン処理からは solve(original, cloned, target) を呼び出し、その結果を返します

このアルゴリズムの計算量は O(n)（n はノード数）であり、各ノードを一度だけ訪問すればよいため、非常に効率的です。また、必要な追加メモリも再帰のスタック分だけで済みます。

C++による実装例

それでは、以下の実装コードを見て、より深く理解しましょう。

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
         temp->left = new TreeNode(val);
      else
         temp->left = new TreeNode(0);
      return;
      } else {
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      } else {
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
   public:
   TreeNode* solve(TreeNode* node1, TreeNode* node2, TreeNode*
   target){
      if(!node1) return NULL;
      if(node1 == target && node1->val == node2->val) return node2;
      TreeNode* leftPart = solve(node1->left, node2->left, target);
      TreeNode* rightPart = solve(node1->right, node2->right, target);
      return leftPart? leftPart : rightPart;
   }
   TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned,
   TreeNode* target) {
      return solve(original, cloned, target);
   }
};
main(){
   vector<int> v = {7,4,3,NULL,NULL,6,19};
   TreeNode *root = make_tree(v);
   TreeNode *cloned = make_tree(v);
   TreeNode *target = root->right; //The node with value 3
   Solution ob;
   cout << (ob.getTargetCopy(root, cloned, target))->val;
}

入力

[7,4,3,null,null,6,19]
3

出力

3

このコードでは、まず補助関数 make_tree() を使って入力ベクターから二分木を構築し、元の木とクローン木の2本を作成しています。その後、値が 3 のノード（root の右の子）を target として設定し、getTargetCopy() を呼び出すことで、クローン木における対応するノードを取得しています。実行結果として 3 が出力されれば、正しくノードを特定できています。