C++で先行順走査（プレオーダー）から二分探索木（BST）の後行順走査（ポストオーダー）を求める方法

この問題では、二分探索木（BST：Binary Search Tree）の先行順走査（プレオーダートラバーサル）を表す配列 preOrder[] が与えられます。求めるのは、この先行順走査の情報だけをもとに後行順走査（ポストオーダートラバーサル）を導き出すことです。

入出力例で問題を理解しよう

入力

preOrder[] = {5, 2, 4, 7, 12}

出力

{4, 2, 12, 7, 5}

解決アプローチ

最もシンプルな解法は、与えられた先行順走査から実際にBSTを構築し、その木に対して後行順走査を行うことです。確かにこの方法でも正しい答えは得られますが、木を明示的に構築しなくても済む、より効率的なアプローチがあります。

その鍵となるのが、値の範囲（下限・上限）を設定しながら先行順配列を走査するという手法です。これにより、どの要素が左部分木に属し、どの要素が右部分木に属するかを切り分けられます。

まず、それぞれの走査の順序を確認しておきましょう。

先行順（preOrder）　： 根 -> 左 -> 右
後行順（postOrder）： 左 -> 右 -> 根

先行順の最初の要素は必ず根（ルート）です。この根に対する許容範囲は {INT_MIN, Root} となります。その後、先頭から順に配列を読み進めながら、現在の範囲に収まる要素を再帰的に処理していきます。まず左部分木の範囲で再帰呼び出しを行い、次に右部分木の範囲で同様に処理します。そして各ノードについては、左右の子の処理が完了した後に値を出力すれば、それがまさに後行順の出力順序になります。

解法1：再帰を用いた効率的な実装

C++プログラム例

#include <iostream>
using namespace std;
void findPostOrderTraversalRec(int pre[], int n, int lowerLimit, int
upperLimit, int& index){
    if (index == n)
       return;
    if (pre[index] < lowerLimit || pre[index] > upperLimit)
       return;
    int currNode = pre[index];
    index++;
    findPostOrderTraversalRec(pre, n, lowerLimit, currNode, index);
    findPostOrderTraversalRec(pre, n, currNode, upperLimit, index);
   cout<<currNode<<" ";
}
void findPostOrderTraversalFromPreOrder(int pre[], int n){
    int index = 0;
    findPostOrderTraversalRec(pre, n, -1000, 1000, index);
}
int main(){
    int pre[] = { 5, 2, 4, 7, 12 };
    int n = sizeof(pre) / sizeof(pre[0]);
    cout<<"PreOrder Traversal : \t";
    for(int i = 0; i < n ; i++)
       cout<<pre[i]<<" ";
    cout<<endl<<"Post Order Traversal : \t";
    findPostOrderTraversalFromPreOrder(pre, n);
    return 0;
}

実行結果

PreOrder Traversal − 5 2 4 7 12
Post Order Traversal − 4 2 12 7 5

この再帰的な手法は、BSTを実際に構築することなく O(n) の時間計算量で後行順走査を求められるため、非常に効率的です。

解法2：反復（イテレーティブ）を用いた実装

もうひとつの方法として、ループだけで完結する反復型の解法もあります。先行順が「根 → 左 → 右」、後行順が「左 → 右 → 根」であることを利用し、ピボット要素（左部分木の末尾にあたる位置）をあらかじめ計算しておきます。

具体的には、先頭の根の値より大きい値を持つ最初の要素のインデックスを探すことでピボットを特定できます。こうして得られたピボットを基準に、「左部分木の要素 → 右部分木の要素 → 根」の順に出力すれば、それがそのまま後行順走査になります。

C++プログラム例

#include <iostream>
using namespace std;
void findPostOrderTraversalFromPreOrder(int pre[], int n){
    int pivot = 0;
    for(int i = 1; i < n; i++){
       if (pre[0] <= pre[i]) {
          pivot = i;
          break;
       }
    }
    for(int i = pivot - 1; i > 0; i--){
       cout << pre[i] << " ";
    }
    for(int i = n - 1; i >= pivot; i--) {
       cout << pre[i] << " ";
    }
    cout << pre[0];
}
int main(){
    int pre[] = { 5, 2, 4, 7, 12 };
    int n = sizeof(pre) / sizeof(pre[0]);
    cout<<"PreOrder Traversal : \t";
    for(int i = 0; i < n ; i++)
       cout<<pre[i]<<" ";
    cout<<endl<<"Post Order Traversal : \t";
    findPostOrderTraversalFromPreOrder(pre, n);
    return 0;
}

実行結果

PreOrder Traversal − 5 2 4 7 12
Post Order Traversal − 4 2 12 7 5

まとめ

BSTの先行順走査から後行順走査を求めるには、①値の範囲を使った再帰的アプローチ、②ピボットを利用した反復的アプローチの2つの方法があります。どちらも木を明示的に構築せずに結果を得られる点がポイントです。特に再帰版は範囲チェックによって部分木の境界を自然に判定できるため、任意のBST形状にも柔軟に対応できます。