C++で文字列から二分木を構築する方法

括弧と整数から構成される文字列が与えられたとき、その文字列から二分木を構築する問題を考えてみましょう。入力文字列全体が一つの二分木を表しており、整数の後に0個、1個、または2組の括弧が続く形式になっています。整数はルート（根）ノードの値を表し、各括弧のペアは同じ構造を持つ子の部分木を含んでいます。

問題の例

例えば、入力が "4(2(3)(1))(6(5))" のような文字列だった場合、出力は [3,2,1,4,5,6]（中順走査・inorder traversal の結果）となります。

解決アプローチ

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

• 再帰関数 solve() を定義します。引数として文字列 s と現在のインデックス idx（参照渡し）を受け取ります。
• idx が文字列の長さ以上の場合、null を返します。
• 空の文字列 num を用意します。
• idx が文字列の範囲内であり、かつ s[idx] が '(' でも ')' でもない間、以下を繰り返します。
  • num に s[idx] の文字を追加します。
  • idx を1つ進めます。
• num の値を持つ新しいノードを作成します。
• idx が文字列の範囲内で、かつ s[idx] が '(' と等しい場合：
  • idx を1つ進めます。
  • ノードの左の子を solve(s, idx) の結果とします。
  • idx を1つ進めます（閉じ括弧をスキップ）。
  • さらに idx が範囲内で s[idx] が '(' と等しい場合：
    • idx を1つ進めます。
    • ノードの右の子を solve(s, idx) の結果とします。
    • idx を1つ進めます。
• 作成したノードを返します。

メイン処理の流れ

• idx を 0 に初期化します。
• solve(s, idx) を呼び出し、その結果を返します。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#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 inord(TreeNode *root){
   if(root != NULL){
      inord(root->left);
      cout << root->val << " ";
      inord(root->right);
   }
}
class Solution {
public:
   TreeNode* solve(string s, int& idx){
      if (idx >= s.size())
         return NULL;
      string num = "";
      while (idx < s.size() && s[idx] != '(' && s[idx] != ')') {
         num += s[idx];
         idx++;
      }
      TreeNode* node = new TreeNode(stoi(num));
      if (idx < s.size() && s[idx] == '(') {
         idx++;
         node->left = solve(s, idx);
         idx++;
         if (idx < s.size() && s[idx] == '(') {
            idx++;
            node->right = solve(s, idx);
            idx++;
         }
      }
      return node;
   }
   TreeNode* str2tree(string s) {
      int idx = 0;
      TreeNode* temp = new TreeNode(-1);
      return solve(s, idx);
   }
};
main(){
   Solution ob;
   TreeNode *root = ob.str2tree("4(2(3)(1))(6(5))");
   inord(root);
}

入力

"4(2(3)(1))(6(5))"

出力

3 2 1 4 5 6

まとめ

このアルゴリズムは、文字列を先頭から走査しながら再帰的に木構造を組み立てるシンプルな手法です。数字を読み取ってノードを作成し、開き括弧 '(' が見つかるたびに左の子、次に右の子を再帰的に構築します。時間計算量は O(n)、空間計算量も再帰の深さに応じて O(n) となり、効率的に二分木を復元できます。