C++で二分木を単一リンクリストに変換するプログラム

二分木が与えられたとき、それをその場（in-place）で単一リンクリストに変換することを考えます。ここでの「その場」とは、追加のノードを生成せず、既存のノードのポインタを付け替えるだけで変換を行うことを意味します。

例えば、次のような二分木が入力として与えられた場合：

出力は以下のように、すべてのノードが右側のポインタだけで連結されたリンクリストになります：

解法のアプローチ

この問題を解くために、以下の手順に従います。

• ポインタ prev を null で初期化します。これは「直前に処理したノード」を保持するためのものです。
• ルートを引数にとる再帰関数 solve() を定義します。
• ルートが null の場合は何もせずに返ります。
• まず右部分木に対して再帰的に solve() を呼び出します。
• 次に左部分木に対して再帰的に solve() を呼び出します。
• 現在のノードの right を prev に設定し、left を null にします。
• 最後に prev を現在のノードに更新します。

この手法のポイントは、逆順の後行順走査（post-order traversal）を使うことです。つまり、右→左→自分自身の順に処理することで、リンクを張り替える際にまだ処理していないノードへの参照を失わずに済みます。結果として、ノードは元の木における先行順（pre-order）と同じ順序、すなわち「1, 2, 3, 4, 5」のように連結されます。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
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:
   TreeNode* prev = NULL;
   void flatten(TreeNode* root) {
      if(!root) return;
         flatten(root->right);
      flatten(root->left);
      root->right = prev;
      root->left = NULL;
      prev = root;
   }
};
main(){
   vector<int> v = {1,2,5,3,4};
   TreeNode *root = make_tree(v);
   Solution ob;
   (ob.flatten(root));
   TreeNode *ptr = root;
   while(ptr != NULL && ptr->val != 0){
      cout << ptr->val << ", ";
      ptr = ptr->right;
   }
}

入力

{1,2,5,3,4}

出力

1, 2, 3, 4, 5,

コードの解説

このプログラムは大きく分けて3つの部分から構成されています。

1. 木の構築部分

make_tree() 関数は、整数のベクターを受け取り、レベル順（幅優先）にノードを挿入して二分木を構築します。insert() 関数はキューを使って空いている位置（左→右の順）に新しいノードを追加していきます。

2. 変換処理（flatten）

Solution クラスの flatten() メソッドがこの問題の核心です。メンバ変数 prev が直前に処理したノードを記憶しており、再帰的に右・左の部分木を先に処理した後、現在のノードの right ポインタを prev につなぎ替えます。こうすることで、すべてのノードが右ポインタのみで鎖状につながったリンクリストが完成します。

3. 結果の出力

main() 関数では、変換後のリンクリストを先頭ノードから right ポインタをたどりながら順に出力し、正しく変換できているかを確認しています。

計算量についても触れておくと、各ノードを一度だけ訪問するため時間計算量は O(n)、再帰呼び出しによるスタック領域が必要なため空間計算量は O(h)（h は木の高さ）となります。