C++で二分木における最も深い奇数レベルの葉ノードの深さを求める方法

二分木の中で「奇数レベル」に存在する葉ノードのうち、最も深い位置にあるものの深さを求めるアルゴリズムを、C++のコード例とともに解説します。

ツリーノード構造体の定義

まず、int型のキーと左右の子ノードへのポインタを持つ、ツリーノードを表す構造体を定義します。最初に作成されたノードはルートノードとなり、それ以降に作成されるノードは子ノードとして扱われます。

struct Node {
    int data;
    struct Node *leftChild, *rightChild;
};

createNode関数の実装

次に、createNode(int key)関数を作成します。この関数はint型のキー値を受け取り、ノードのdataメンバーに代入します。戻り値としては、生成されたNode構造体へのポインタを返します。また、新しく作成されたノードの左子・右子はどちらもNULLに初期化されます。

Node* createNode(int data){
    Node* node = new Node;
    node->data = data;
    node->leftChild = node->rightChild = NULL;
    return node;
}

isLeaf関数の実装

続いて、isLeaf(Node *currentNode)関数を定義します。この関数は引数として受け取ったノードが子を持たないかどうかを判定し、葉ノードであればtrue、そうでなければfalseを返します。

bool isLeaf(Node *currentNode){
    return (currentNode->leftChild == NULL &&
    currentNode->rightChild == NULL);
}

deepestOddLvlDepth関数の実装

deepestOddLvlDepth(Node *currentNode, int currentLevel=0)関数は、現在のノードと現在のレベルを引数として受け取ります。currentLevelにはデフォルト引数として0が設定されているため、呼び出し時に値を渡さなくても動作します。currentNodeがNULLの場合は0を返します。

再帰呼び出しが行われるたびにcurrentLevelは1ずつ増加し、ベース条件が満たされるまで処理が繰り返されます。その後、現在のノードが「奇数レベルの葉ノード」であるかどうかを判定します。左右の子を順に辿ることで最も深い奇数レベルの葉ノードの深さを求め、leftChildLevelとrightChildLevelの最大値をmain関数へ返して結果を出力します。

int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
    if ( currentNode == NULL)
        return 0;
    currentLevel ++;
    if ( currentLevel % 2 != 0 && isLeaf(currentNode))
        return currentLevel;
    int leftChildLevel = deepestOddLvlDepth(currentNode->leftChild,currentLevel);
    int rightChildLevel = deepestOddLvlDepth(currentNode->rightChild,currentLevel);
    return max(leftChildLevel,rightChildLevel);
}

なお、このアルゴリズムは木のすべてのノードを一度ずつ訪問するため、計算量はノード数をNとするとO(N)になります。

サンプルコード全体

以下に、二分木における最も深い奇数レベルの葉ノードの深さを求める完全な実装例を示します。

#include<iostream>
using namespace std;
struct Node{
    int key;
    struct Node *leftChild, *rightChild;
};
Node* createNode(int key){
    Node* node = new Node;
    node->key = key;
    node->leftChild = node->rightChild = NULL;
    return node;
}
bool isLeaf(Node *currentNode){
    return (currentNode->leftChild == NULL &&
    currentNode->rightChild == NULL);
}
int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
    if ( currentNode == NULL)
        return 0;
    currentLevel ++;
    if ( currentLevel % 2 != 0 && isLeaf(currentNode))
        return currentLevel;
    int leftChildLevel = deepestOddLvlDepth(currentNode->leftChild,currentLevel);
    int rightChildLevel = deepestOddLvlDepth(currentNode->rightChild,currentLevel);
    return max(leftChildLevel,rightChildLevel);
}
int main(){
    Node *root = createNode(15);
    root->leftChild = createNode(33);
    root->rightChild = createNode(18);
    root->rightChild->leftChild = createNode(19);
    root->rightChild->rightChild = createNode(20);
    root->rightChild->rightChild->leftChild = createNode(28);
    root->rightChild->rightChild->rightChild = createNode(29);
    cout << "The depth of the deepest odd level leaf node is: "<<deepestOddLvlDepth(root) << endl;
    return 0;
}

実行結果

このサンプルでは、ルート（15）をレベル1とし、33と18がレベル2、19と20がレベル3、28と29がレベル4に配置されています。葉ノードの中で奇数レベルに属するのは19（レベル3）のみのため、結果は3となります。上記のコードを実行すると、次の出力が得られます。

The depth of the deepest odd level leaf node is: 3