C++で二分木の指定した垂直レベルがソート済みかどうかを判定する方法

概要

二分木が与えられたとき、その二分木の指定された垂直レベル(vertical level)がソートされているかどうかを判定するのが本記事の目的です。

なお、複数のノードが同じ位置で重なっている場合は、それらのノードが属するレベル内でソート済みの列を形成しているかどうかを確認します。

入力例

2
/ \
3 6
/ \
8 5
  /
7
Level l = -1

出力例

Yes

レベル -1 に属するノードは 3 → 7 の順に並んでおり、これはソート済みの列となっています。

入力例(ノードの重なりがある場合)

2
/ \
3 7
\ /
4 5
Level l = 0

出力例

Yes

この例では、値 4 と 5 を持つノードが二分木上で重なっている点に注目してください。

このような場合でも、レベルごとにソート済みの列を形成しているかを検証します。レベル 0 に属するノードは 2 → 4 → 5 の順であり、これもソート済みの列とみなせます。

アプローチ

単純な解法

最も単純な方法は、まず二分木に対してレベル順走査(level order traversal)を行い、各垂直レベルごとに別々の配列へノードを格納することです。その後、レベル l に対応する配列がソートされているかどうかを確認します。ただし、この手法はメモリ消費量が大きくなるため、改善の余地があります。

効率的な解法

より効率的な方法では、二分木を垂直レベル順に走査しながら、レベル l 上のノードの値だけを追跡します。直前の要素が現在の要素以下であれば、ソート済みの列が保たれていることになります。

具体的には、垂直方向の走査を実行中に直前の値を保持しておき、レベル l 上の現在のノードの値と比較します。現在のノードの値が直前の値以上であれば、レベル l の終端に達するまで同じ手順を繰り返します。途中で現在のノードの値が直前の値より小さくなった時点で、レベル l はソートされていないと判断できます。逆に、レベル l の終端まで到達できれば、そのレベルはソート済みであるといえます。

実装例(C++)

// 二分木の垂直レベル l が
// ソートされているかどうかを判定する
// C++ プログラム
#include <bits/stdc++.h>
using namespace std;

// 木のノードを表す構造体
struct Node1 {
   int key1;
   Node1 *left1, *right1;
};

// 新しい木のノードを作成する関数
Node1* newNode(int key1){
   Node1* temp1 = new Node1;
   temp1->key1 = key1;
   temp1->left1 = temp1->right1 = NULL;
   return temp1;
}

// 指定された二分木の垂直レベル l が
// ソートされているかどうかを判定する
// ヘルパー関数
bool isSorted1(Node1* root1, int level1){
   // ルートが NULL の場合、答えは空の部分集合となり、
   // 空の部分集合は常にソート済みとみなされる
   if (root1 == NULL)
      return true;

   // 垂直レベル l 内の直前の値を保持する変数
   int prevVal1 = INT_MIN;

   // 垂直方向の走査中の現在のレベルを保持する変数
   int currLevel1;

   // 垂直方向の走査中の現在のノードを保持する変数
   Node1* currNode1;

   // 垂直順走査を行うためのキューを宣言。
   // キューの要素には pair を使用し、
   // first がノード、second がそのノードの
   // 垂直レベルを表す
   queue<pair<Node1*, int>> q1;

   // ルートをキューに挿入。ルートの垂直レベルは 0
   q1.push(make_pair(root1, 0));

   // すべてのノードを訪問し終えるまで
   // 垂直順走査を続ける
   while (!q1.empty()) {
      currNode1 = q1.front().first;
      currLevel1 = q1.front().second;
      q1.pop();

      // キューから取り出したノードのレベルが
      // 目的のレベルかどうかを確認。目的のレベルであれば、
      // そのレベル内の直前の値がノードの値以下かを検証
      if (currLevel1 == level1) {
         if (prevVal1 <= currNode1->key1)
            prevVal1 = currNode1->key1;
      else
         return false;
   }

   // 左の子が NULL でなければ、
   // レベルを 1 減らしてキューに追加
   if (currNode1->left1)
      q1.push(make_pair(currNode1->left1, currLevel1 - 1));

   // 右の子が NULL でなければ、
   // レベルを 1 増やしてキューに追加
   if (currNode1->right1)
      q1.push(make_pair(currNode1->right1, currLevel1 + 1));
   }

   // 問い合わせたレベルが二分木中に存在しない場合、
   // そのレベルは空の部分集合となるため、
   // 答えは true となる
   return true;
}

// ドライバープログラム
int main(){
/*
      2
      / \
      3 6
      / \
      8 5
        /
      7
*/
   Node1* root1 = newNode(2);
   root1->left1 = newNode(3);
   root1->right1 = newNode(6);
   root1->left1->left1 = newNode(8);
   root1->left1->right1 = newNode(5);
   root1->left1->right1->left1 = newNode(7);

   int level1 = -1;
   if (isSorted1(root1, level1) == true)
      cout << "Yes";
   else
      cout << "No";
   return 0;
}

出力

Yes

まとめ

このアルゴリズムでは、キューを用いた幅優先探索(BFS)をベースに垂直順走査を実現し、対象レベルのノードのみを逐次比較することで、余分なメモリを使用せずにソートの判定を行えます。計算量は木の全ノード数に比例する O(n)、補助的なメモリも O(n) 程度に抑えられるため、実用的な実装といえます。