C++で反転木がtargetの部分木と一致するかを判定する方法

ここでは、source と target という2つの二分木が与えられ、source を反転(inversion)した木 T のうちの何れかが target の部分木になっているかどうかを判定する問題を扱います。言い換えれば、target の中に、T と値および構造が完全に一致し、そのすべての子孫ノードまで含めて同一であるようなノードが存在するかを確認するということです。

反転木とは?

ある木が別の木の「反転」であるとは、次のいずれかの条件を満たす場合を指します。

• 両方の木が空(ヌル)である
• 左右の子を必要に応じてスワップしてもよく、かつその左部分木と右部分木が互いに反転関係にある

例として、入力が次のような source だったとします。

target は以下の通りです。

この場合、出力は True になります。source の一部のノードで左右の子を入れ替えることで、target 内の部分木と完全に一致させられるためです。

解決のためのアルゴリズム

この問題を解くには、次の手順に従います。

check() 関数(node1 と node2 を受け取る)

2つのノードを比較し、左右を入れ替えた一致も許容して判定する補助関数です。

• node1 と node2 がどちらも NULL の場合は true を返す
• node1 または node2 のどちらか一方だけが NULL の場合は false を返す
• node1 の val と node2 の val が等しくない場合は false を返す
• op1 := check(node1 の左, node2 の左) AND check(node1 の右, node2 の右)(そのままの向きで一致するか)
• op2 := check(node1 の右, node2 の左) AND check(node1 の左, node2 の右)(左右を反転して一致するか)
• op1 と op2 の少なくとも一方が true であれば true を返す

solve() 関数(source と target を受け取る)

target の各ノードを候補の根として順番に試す本体の関数です。

• source と target がどちらも空の場合は true を返す
• source または target のどちらか一方だけが NULL の場合は false を返す
• op1 := check(target, source)(現在の target ノードを根として比較)
• op1 が true であれば true を返す
• solve(source, target の左部分木) または solve(source, target の右部分木) の少なくとも一方が true であれば true を返す

C++実装例

より理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data) {
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
   public:
   bool check(TreeNode* node1, TreeNode* node2){
      if(!node1 && !node2)
      return true;
      if(!node1 || !node2)
      return false;
      if(node1->val != node2->val) {
         return false;
      }
      bool op1 = check(node1->left, node2->left) && check(node1->right, node2->right);
      bool op2 = check(node1->right, node2->left) && check(node1->left, node2->right);
      return op1 || op2;
   }
   bool solve(TreeNode* source, TreeNode* target) {
      if(!target && !source)
         return true;
      if(!target || !source)
         return false;
      bool op1 = check(target, source);
      if(op1)
         return true;
      return solve(source, target->left) || solve(source, target->right);
   }
};
main(){
   Solution ob;
   TreeNode *target = new TreeNode(6);
   target->left = new TreeNode(3);
   target->right = new TreeNode(1);
   target->right->left = new TreeNode(3);
   target->right->right = new TreeNode(2);
   target->right->right->left = new TreeNode(4);
   TreeNode *source = new TreeNode(1);
   source->left = new TreeNode(2);
   source->right = new TreeNode(3);
   source->left->right = new TreeNode(4);
   cout << (ob.solve(source, target));
}

入力

TreeNode *target = new TreeNode(6);
target->left = new TreeNode(3);
target->right = new TreeNode(1);
target->right->left = new TreeNode(3);
target->right->right = new TreeNode(2);
target->right->right->left = new TreeNode(4);
TreeNode *source = new TreeNode(1);
source->left = new TreeNode(2);
source->right = new TreeNode(3);
source->left->right = new TreeNode(4);

出力

1

出力の「1」は true を表しています。つまり、source を適切に反転させることで、target 内の部分木と一致させることができたという意味です。計算量の目安としては、target の各ノードに対して check() が最大 O(source のノード数) で動作するため、全体で O(N × M)(N は target、M は source のノード数)となります。