C++による二分木の垂直順序走査

二分木が与えられたとき、そのノードの値を垂直順序で走査する問題について解説します。同じ行と列に複数のノードがある場合は、左から右の順序で出力します。

問題の例

以下のような二分木を考えます。

この木に対する垂直順序走査の結果は [[9], [3, 15], [20], [7]] となります。

アルゴリズム

1. 水平距離（x座標）をキーとするマップ m を定義する。値はノードの値のリスト。
2. 再帰関数 solve(node, x) を定義し、深さ優先探索でノードをマップに登録する。
   • ノードが null の場合は終了
   • 左の子を x - 1 で再帰呼び出し
   • 右の子を x + 1 で再帰呼び出し
   • 現在のノードの値を m[x] に追加
3. メイン処理では幅優先探索（BFS）を用いてレベル順に処理し、同じ位置のノードは左から右の順で格納されるようにする。
   • ルートが null なら空配列を返す
   • キューに {0, root} を入れ、m[0] にルートの値を追加
   • キューが空になるまで繰り返し:
     • 現在のキューのサイズ分だけ処理（レベルごとの処理）
     • 先頭要素を取り出し、ノードと x 座標を取得
     • 左の子があれば {x - 1, left} をキューに入れ、m[x - 1] に値を追加
     • 右の子があれば {x + 1, right} をキューに入れ、m[x + 1] に値を追加
4. マップのキー順（左から右）で値を取り出し、二次元配列として返す

C++ 実装例

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[";
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = NULL;
        right = NULL;
    }
};

void insert(TreeNode **root, int val) {
    queue<TreeNode*> q;
    q.push(*root);
    while (q.size()) {
        TreeNode *temp = q.front();
        q.pop();
        if (!temp->left) {
            if (val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        } else {
            q.push(temp->left);
        }
        if (!temp->right) {
            if (val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        } else {
            q.push(temp->right);
        }
    }
}

TreeNode* make_tree(vector<int> v) {
    TreeNode *root = new TreeNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        insert(&root, v[i]);
    }
    return root;
}

class Solution {
public:
    map<int, vector<int>> m;
    
    void solve(TreeNode* node, int x = 0) {
        if (!node || node->val == 0)
            return;
        solve(node->left, x - 1);
        solve(node->right, x + 1);
        m[x].push_back(node->val);
    }
    
    static bool cmp(vector<int>& a, vector<int>& b) {
        return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1];
    }
    
    vector<vector<int>> verticalOrder(TreeNode* root) {
        if (!root)
            return {};
        queue<pair<int, TreeNode*>> q;
        q.push({ 0, root });
        m[0].push_back(root->val);
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                pair<int, TreeNode*> curr = q.front();
                q.pop();
                TreeNode* node = curr.second;
                int x = curr.first;
                if (node->left && node->left->val != 0) {
                    q.push({ x - 1, node->left });
                    m[x - 1].push_back(node->left->val);
                }
                if (node->right && node->right->val != 0) {
                    q.push({ x + 1, node->right });
                    m[x + 1].push_back(node->right->val);
                }
            }
        }
        vector<vector<int>> ret;
        for (auto it = m.begin(); it != m.end(); ++it) {
            ret.push_back(it->second);
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3, 9, 20, NULL, NULL, 15, 7};
    TreeNode *root = make_tree(v);
    print_vector(ob.verticalOrder(root));
    return 0;
}

実行結果

入力

{3, 9, 20, NULL, NULL, 15, 7}

出力

[[9], [3, 15], [20], [7]]

解説のポイント

• 水平距離（Horizontal Distance）: ルートを 0 とし、左へ行くたびに -1、右へ行くたびに +1 する
• BFS（幅優先探索）: 同じ垂直線上のノードを上から下、左から右の順で処理するために使用
• map（順序付きマップ）: キー（水平距離）が自動的にソートされるため、左から右への出力が容易
• 計算量: 時間計算量 O(N log N)、空間計算量 O(N)（N はノード数）