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

括弧と整数で構成される文字列があるとします。その文字列から二分木を構築する必要があります。入力全体が二分木を表します。これは、0、1、または2組の括弧が後に続く整数を保持します。整数はルートの値を表し、括弧のペアには同じ構造の子二分木が含まれます。

したがって、入力が「4（2（3）（1））（6（5））」の場合、出力は[3,2,1,4,5,6]（順序付き走査）になります

これを解決するには、次の手順に従います-

• 関数solve（）を定義します。これには、s、idx、

  が必要です。

• idx> =sのサイズの場合、-

  • nullを返す

• num：=空の文字列

• while（idx

  • num：=num + s [idx]

  • （idxを1増やします）

• node=値numの新しいノード

• idx

  • （idxを1増やします）

  • ノードの左側：=resolve（s、idx）

  • （idxを1増やします）

  • idx

    • （idxを1増やします）

    • ノードの右側：=resolve（s、idx）

    • （idxを1増やします）

• リターンノード

• メインの方法から、次のようにします-

• idx：=0

• temp=値が-1の新しいノード

• リターンソルブ（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