C++でプレオーダートラバーサルからツリーを回復する

このトラバーサルの各ノードで、出力はD個のダッシュ（ここでDはこのノードの深さ）になり、その後、このノードの値が表示されます。ノードの深さがDであるかどうかはわかっているので、その直接の子の深さはD + 1であり、ルートノードの深さは0です。

ノードに子が1つしかない場合、その子は左の子であることが保証されることを覚えておく必要があります。したがって、このトラバーサルの出力Sが与えられた場合は、ツリーを回復してそのルートを返します。

したがって、入力が「1-2--3--4-5--6--7」の場合、出力は

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

• 1つのスタックstを定義する

• i：=0、n：=Sのサイズ

• lvl：=0、num：=0

• i

  • 初期化レベル：=0の場合、S[i]が'-'と同じ場合、更新（レベルを1増やす）、（iを1増やす）、実行-

    • 何もしない

  • num：=0

  • （i

    • num：=num * 10 +（S [i]-'0'）

    • （iを1増やします）

  • st> lvlのサイズで、実行-

    • stから要素を削除

  • temp=num値で新しいツリーノードを作成します

  • stが空でなく、stの上部要素の左側がnullでない場合、-

    • stの一番上の要素の左側：=temp

  • それ以外の場合、stが空でない場合は、-

    • stの一番上の要素の右側：=temp

  • stにtempを挿入

• st> 1のサイズで、実行-

  • stから要素を削除

• return（stが空の場合はNULL、それ以外の場合はstの最上位要素）

理解を深めるために、次の実装を見てみましょう-

例

#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* recoverFromPreorder(string S) {
      stack<TreeNode*> st;
      int i = 0;
      int n = S.size();
      int lvl = 0;
      int num = 0;
      while (i < n) {
         for (lvl = 0; S[i] == '-'; lvl++, i++)
         ;
         num = 0;
         while (i < n && S[i] != '-') {
            num = num * 10 + (S[i] - '0');
            i++;
         }
         while (st.size() > lvl)
         st.pop();
         TreeNode* temp = new TreeNode(num);
         if (!st.empty() && !st.top()->left) {
            st.top()->left = temp;
         }
         else if (!st.empty()) {
            st.top()->right = temp;
         }
         st.push(temp);
      }
      while (st.size() > 1)
      st.pop();
      return st.empty() ? NULL : st.top();
   }
};
main(){
   Solution ob;
   TreeNode *root = ob.recoverFromPreorder("1-2--3--4-5--6--7");
   inord(root);
}

入力

"1-2--3--4-5--6--7"

出力

3 2 4 1 6 5 7