C++で二分木の「いとこ」ノードを判定するアルゴリズム

二分木のいとこ（Cousins）とは

二分木において、根ノードは深さ0に位置し、深さkのノードの子は深さk+1に位置するとします。

このとき、二分木内の2つのノードが同じ深さを持ち、かつ親が異なる場合、その2つのノードは「いとこ（cousins）」であると定義されます。

木の中のすべての値は一意であり、異なる2つのノードの値としてxとyが与えられます。私たちの課題は、値xとyに対応するノードがいとこの関係にあるかどうかを判定することです。

例えば、次のような二分木が与えられたとします。

x = 5、y = 4 の場合、出力は true となります。両者とも深さ2にありますが、親がそれぞれ異なるためです。

解法のアプローチ

この問題を解くために、幅優先探索（BFS）を利用した以下の手順に従います。

• マップ um を1つ定義します（値から親ノードへの対応を記録）。
• キュー q を1つ定義します。
• 根ノードを q に挿入します。
• um[x] := um[y] := NULL と初期化します。
• q が空になるまで、以下を繰り返します。
  • qSize := q のサイズ
  • qSize > 0 の間（1回ごとに qSize を減らしながら）、以下を実行します。
    • cur := q の先頭要素
    • q から要素を削除します。
    • cur の左の子が存在する場合
      • um に左の子の値が登録済みなら、um[左の子の値] := cur とします。
      • そうでなければ、cur の左の子を q に挿入します。
    • cur の右の子が存在する場合も同様に処理します。
      • um に右の子の値が登録済みなら、um[右の子の値] := cur とします。
      • そうでなければ、cur の右の子を q に挿入します。
  • um[x] または um[y] が非ゼロの場合（どちらかが見つかった場合）
    • um[x] が 0、または um[y] が 0、または um[x] == um[y] の場合は false を返します（片方だけ見つかった、または同じ親を持つ兄弟のケース）。
    • それ以外の場合は true を返します。
• ループを抜けたら false を返します。

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 isCousins(TreeNode *root, int x, int y) {
      unordered_map<int, TreeNode *> um;
      queue<TreeNode *> q;
      q.push(root);
      um[x] = um[y] = NULL;
      while (!q.empty()) {
         int qSize = q.size();
         while (qSize-- > 0) {
            auto cur = q.front();
            q.pop();
            if (cur->left && cur->left->val != 0)
               if (um.count(cur->left->val))
                  um[cur->left->val] = cur;
               else
                  q.push(cur->left);
            if (cur->right && cur->right->val != 0)
               if (um.count(cur->right->val))
                  um[cur->right->val] = cur;
               else
                  q.push(cur->right);
         }
         if (um[x] or um[y])
            if (!um[x] or !um[y] or um[x] == um[y])
               return false;
            else
               return true;
      }
      return false;
   }
};
main() {
   Solution ob;
   TreeNode *root = new TreeNode(1);
   root->left = new TreeNode(2); root->right = new TreeNode(3);
   root->left->right = new TreeNode(4); root->right->right = new TreeNode(5);
   cout << (ob.isCousins(root, 5, 4));
}

入力

TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2); root->right = new TreeNode(3);
root->left->right = new TreeNode(4); root->right->right = new
TreeNode(5);
cout << (ob.isCousins(root, 5, 4));

出力

1

まとめ

このアルゴリズムでは、BFSを使って木をレベルごとに走査し、各レベルでxとyの親ノードを記録しています。同じレベルで両方が見つかり、かつ親が異なれば「いとこ」と判定できます。計算量はO(n)、空間計算量もO(n)であり、二分木の走査問題としては効率的な解法です。