二分木で屈曲数が最大となるパスの長さを求めるC++プログラム

本記事では、二分木が与えられたときに、屈曲数が最大となるパスを求める問題を解いていきます。ここで「屈曲(ベンド)」とは、パスの進行方向が左から右へ、または右から左へと切り替わる箇所のことです。具体例を見てみましょう。

入力 −

出力 −

6

この方法では、木を走査しながら直前の移動方向を記録していきます。方向が変化した時点で屈曲数を加算し、最終的にその最大値を求めます。

解法のアプローチ

このアプローチでは、すべてのパスを辿り、各パスにおける屈曲の総数を計算します。葉ノードに到達した時点で、これまでの屈曲数が現在の最大値を上回っていれば、答えとパスの長さを新しい値に更新します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
struct Node { // ノードの構造体
    int key;
    struct Node* left;
    struct Node* right;
};
struct Node* newNode(int key){ // ノードの初期化
    struct Node* node = new Node();
    node->left = NULL;
    node->right = NULL;
    node->key = key;
    return node;
}
void maximumBends(struct Node* node, char direction, int bends,
                  int* maxBends, int soFar, int* len){
    if (node == NULL) // NULLに到達した場合
        return;
    if (node->left == NULL && node->right == NULL) { // 葉ノードに到達したら答えを更新するか確認
        if (bends > *maxBends) {
            *maxBends = bends;
            *len = soFar;
        }
    }
    else {
        if (direction == 'l') { // 現在の方向が左の場合
            maximumBends(node->left, direction, bends, maxBends, soFar + 1, len);
            maximumBends(node->right, 'r', bends + 1, maxBends, soFar + 1, len); // 方向を変えるので屈曲数も増える
        }
        else {
            maximumBends(node->right, direction, bends, maxBends, soFar + 1, len);
            maximumBends(node->left, 'l', bends + 1, maxBends, soFar + 1, len); // 方向が左の場合と同様の処理
        }
    }
}
int main(){
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(2);
    root->left->left = newNode(3);
    root->left->right = newNode(5);
    root->right->left = newNode(2);
    root->right->left->right = newNode(1);
    root->right->left->right->left = newNode(9);
    int len = 0, bends = 0, maxBends = -1;
    if(!root) // 木が空の場合
        cout << "0\n";
    else{
        if (root->left) // 左部分木が存在する場合
            maximumBends(root->left, 'l', bends, &maxBends, 1, &len);
        if (root->right) // 右部分木が存在する場合
            maximumBends(root->right, 'r', bends, &maxBends, 1, &len);
        cout << len << "\n";
    }
    return 0;
}

出力

4

コードの解説

上記のコードでは、すべてのパスを再帰的に辿りながら、これまでに発生した屈曲の数を数えています。パスの終点である葉ノードに到達した時点で、そこまでの屈曲数が既存の最大値より大きいかどうかを判定し、条件を満たしていれば最大屈曲数とともにパスの長さも新しい値に更新します。プログラムはこの流れで動作します。

まとめ

本チュートリアルでは、屈曲数が最大となるパスの長さを求める問題を取り上げました。この問題を解くためのC++プログラムと、標準的なアプローチについても解説しました。同様のプログラムは、C、Java、Pythonなど他の言語でも実装できます。本チュートリアルが皆様のお役に立てれば幸いです。