【C++】二分木のジグザグ走査(ZigZag Traversal)を2つのスタックで実装する方法

この問題では、二分木(binary tree)が与えられ、その全ノードをジグザグ状(ZigZag)に出力することが求められます。

まず、具体例を使って問題を確認しましょう。

上記の二分木をジグザグ走査すると、各ノードは次の順序で出力されます。

3     5     1     8     7     0     4

1層目は左から右、2層目は右から左…というように、レベルが変わるごとに走査の向きが交互に反転するのがジグザグ走査の特徴です。

解法の考え方

この問題を解くには、二分木をレベル順(幅優先)で走査し、各レベルが終わるたびに走査の向きを反転させます。

ここでは、「現在のレベル用(current)」と「次のレベル用(next)」の2つのスタックと、走査の向きを保持するフラグ変数(order)を利用します。スタックはLIFO(後入れ先出し)の性質を持つため、子ノードを左→右の順でプッシュすれば、次のレベルでは自動的に逆順(右→左)で取り出されます。フラグ変数は、現在のレベルをどちらの向きで処理するかを決める重要な役割を担っています。

アルゴリズムの手順

1. ルートノードを currentlevel スタックにプッシュし、フラグ LtR を true(左から右)で初期化します。
2. currentlevel が空になるまで、以下の処理を繰り返します。
3. currentlevel の先頭ノードを取り出し(pop)、その値を出力します。
4. LtR が true の場合は「左→右」の順、false の場合は「右→左」の順で、子ノードを nextlevel にプッシュします。
5. currentlevel が空になった時点で、フラグ LtR を反転し、currentlevel と nextlevel を入れ替えます。

C++での実装例

上記の考え方を実際に実装したプログラムが次のコードです。

#include <iostream>
#include <stack>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
};
void zigZagTreeTraversal(struct Node* root){
    if (!root)
        return;
    stack<struct Node*> currentlevel;
    stack<struct Node*> nextlevel;
    currentlevel.push(root);
    bool LtR = true;
    while (!currentlevel.empty()) {
        struct Node* temp = currentlevel.top();
        currentlevel.pop();
        if (temp) {
            cout<<temp->data<<"\t";
            if (LtR) {
                if (temp->left)
                    nextlevel.push(temp->left);
                if (temp->right)
                    nextlevel.push(temp->right);
            }
            else {
                if (temp->right)
                    nextlevel.push(temp->right);
                if (temp->left)
                    nextlevel.push(temp->left);
            }
        }
        if (currentlevel.empty()) {
            LtR = !LtR;
            swap(currentlevel, nextlevel);
        }
    }
}
struct Node* insertNode(int data){
    struct Node* node = new struct Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
int main() {
    struct Node* root = insertNode(3);
    root->left = insertNode(1);
    root->right = insertNode(5);
    root->left->left = insertNode(8);
    root->left->right = insertNode(7);
    root->right->left = insertNode(0);
    root->right->right = insertNode(4);
    cout << "ZigZag traversal of the given binary tree is \n";
    zigZagTreeTraversal(root);
    return 0;
}

実行結果

ZigZag traversal of the given binary tree is
3     5     1     8     7     0     4

計算量

• 時間計算量： O(n) — すべてのノードをちょうど1回ずつ訪問するためです(n はノード総数)。
• 空間計算量： O(n) — 最悪の場合、最もノード数の多いレベル分のスタック領域が必要になります。

まとめ

二分木のジグザグ走査は、一般的なレベル順走査(幅優先探索)に「レベルごとに向きを反転させる」というひと工夫を加えたアルゴリズムです。2つのスタックを切り替えて使うことで、特別な反転処理を行わずとも自然にジグザグ順序を実現できます。技術面接でも頻出の定番テーマなので、ぜひ自分で実装できるようにしておきましょう。