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

二分木と値Kが与えられたとき、垂直順走査(Vertical Order Traversal)におけるK番目のノードを出力するのが課題です。該当するノードが存在しない場合は-1を返します。例として、次のような二分木を考えてみましょう。

この二分木を垂直順に走査すると、結果は以下のようになります。

4
2
1 5 6
3 8
7
9

つまり、K = 3 の場合、答えは 1 となります。

アプローチの解説

考え方は非常にシンプルです。まず垂直順走査を実行し、走査中の現在のノードがK番目のノードかどうかを順番に確認していきます。K番目に到達した時点で、そのノードの値を返します。

垂直順走査では、各ノードに水平距離(horizontal distance)を割り当てるのがポイントです。ルートの水平距離を0とし、左の子は親より1小さい値、右の子は親より1大きい値とします。std::mapを使うことで、水平距離の昇順に自動的にソートされた状態でノードを管理できます。さらに、BFS(幅優先探索)をキューを用いて行い、同じ水平距離を持つノードの値をvectorに格納していきます。最後に、mapの先頭から順にノードを数えていき、K番目の値を返せば完成です。

C++での実装例

#include<iostream>
#include<map>
#include<vector>
#include<queue>
using namespace std;
class Node {
    public:
    int key;
    Node *left, *right;
};
Node* getNode(int key){
    Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return node;
}
int findKthNodeVertical(Node* root, int k) {
    if (!root || k == 0)
       return -1;
    int n = 0;
    int k_node = -1;
    map<int, vector<int> > current_map;
    int hd = 0;
    queue<pair<Node*, int> > que;
    que.push(make_pair(root, hd));
    while (!que.empty()) {
       pair<Node*, int> temp = que.front();
       que.pop();
       hd = temp.second;
       Node* node = temp.first;
       current_map[hd].push_back(node->key);
       if (node->left != NULL)
          que.push(make_pair(node->left, hd - 1));
       if (node->right != NULL)
       que.push(make_pair(node->right, hd + 1));
    }
    map<int, vector<int> >::iterator it;
    for (it = current_map.begin(); it != current_map.end(); it++) {
       for (int i = 0; i < it->second.size(); ++i) {
          n++;
          if (n == k)
            return (it->second[i]);
       }
    }
    if (k_node == -1)
       return -1;
}
int main() {
    Node* root = getNode(1);
    root->left = getNode(2);
    root->right = getNode(3);
    root->left->left = getNode(4);
    root->left->right = getNode(5);
    root->right->left = getNode(6);
    root->right->right = getNode(7);
    root->right->left->right = getNode(8);
    root->right->right->right = getNode(9);
    int k = 3;
    cout << "Kth node in vertical traversal: " << findKthNodeVertical(root, k);
}

実行結果

Kth node in vertical traversal: 1

計算量について

このアルゴリズムの時間計算量はO(n log n)です。これは、mapへの挿入操作にlog nのコストがかかるためです。空間計算量はO(n)となり、すべてのノードを格納するために必要なメモリ量に相当します。ノード数が多い場合でも効率的に動作するため、面接や競技プログラミングでもよく使われる定番の手法です。