C++で二分木の対角走査におけるK番目のノードを求める方法

このチュートリアルでは、二分木（バイナリツリー）を対角走査した際の k番目のノード を見つけるプログラムをC++で作成します。

対角走査とは

対角走査では、あるノードから右の子へたどれる範囲を同じ「対角線」上のノードとしてグループ化し、左の子は次の対角線として後から処理します。これにより、木を左上から斜めに切り分けるように順番に訪問することができます。

解決手順

• サンプルデータで二分木を初期化します。
• k の値を設定します。
• キューというデータ構造を使って、二分木を対角的に走査します。
  • 各ノードを訪れるたびに k をデクリメントします。
  • k が 0 になった時点で、そのノードの値を返します。
• 該当するノードが存在しない場合は -1 を返します。

アルゴリズムのポイント

この実装では、キューに NULL を区切り文字として挿入することで、対角線ごとの境界を管理しています。現在の対角線を処理している間に見つかった左の子はすべてキューに追加され、次の対角線の処理対象になります。計算量は時間・空間ともに O(n) です。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *left, *right;
};
Node* getNewNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
int findDiagonalKthElement(Node* root, int k) {
    if (root == NULL || k == 0) {
        return -1;
    }
    int result = -1;
    queue<Node*> q;
    q.push(root);
    q.push(NULL);
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
        if (temp == NULL) {
            if (q.empty()) {
                if (k == 0) {
                    return result;
                }else {
                    break;
                }
            }
            q.push(NULL);
        }else {
            while (temp) {
                if (k == 0) {
                    return result;
                }
                k--;
                result = temp->data;
                if (temp->left) {
                    q.push(temp->left);
                }
                temp = temp->right;
            }
        }
    }
    return -1;
}
int main() {
    Node* root = getNewNode(10);
    root->left = getNewNode(5);
    root->right = getNewNode(56);
    root->left->left = getNewNode(3);
    root->left->right = getNewNode(22);
    root->right->right = getNewNode(34);
    root->right->right->left = getNewNode(45);
    root->left->right->left = getNewNode(67);
    root->left->right->right = getNewNode(100);
    int k = 9;
    cout << findDiagonalKthElement(root, k) << endl;
    return 0;
}

出力

上記のコードを実行すると、次のような結果が得られます。

67

まとめ

本チュートリアルでは、キューを活用することで、二分木の対角走査における k 番目のノードを効率的に求める方法を解説しました。NULL を区切りとして使うテクニックは、レベル順走査など他の木構造の問題にも応用できます。チュートリアルについて不明な点や質問がある場合は、コメント欄でお気軽にお知らせください。