C++のツリーに1行を追加

二分木があり、値vと深さdもあるとすると、指定された深さdに値vのノードの行を追加する必要があります。ルートノードは深さ1にあります。この操作を実行するには、このルールに従う必要があります-

深さdがわかっているので、深さd-1の有効なツリーノードNごとに、値vをNの左サブツリールートと右サブツリールートとして持つ2つのツリーノードを作成する必要があります。また、Nの元の左サブツリーは、新しい左サブツリールートの左サブツリーになり、元の右サブツリーは、新しい右サブツリールートの右サブツリーになります。深さdが1の場合、つまり深さd-1がまったくない場合は、元のツリー全体の新しいルートとして値vを使用してツリーノードを作成します。元のツリーは、新しいルートの左側のサブツリーです。

したがって、入力が次のような場合

その場合、出力は次のようになります

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

• dが1と同じ場合、-

  • temp=値vの新しいノード

  • tempの左側：=root

  • ルート：=temp

• それ以外の場合

  • st

    と呼ばれるペアのスタックを1つ定義します

  • {root、2}をst

    に挿入します

  • lvl：=0

  • 1ペアの温度を定義する

  • （stが空ではない）間、-

    • temp：=stの最上位要素

    • stから要素を削除

    • lvl：=tempの2番目の要素

    • node：=tempの最初の要素

    • lvlがdと同じ場合、-

      • temp1=値vの新しいノード

      • temp2=値vの新しいノード

      • temp1の左側：=ノードの左側

      • temp2の権利：=ノードの権利

      • ノードの左側：=temp1

      • ノードの右側：=temp2

    • それ以外の場合

      • ノードの左側が有効な場合、-

        • {ノードの左側、lvl+1}をst

          に挿入します

      • ノードの権利が有効な場合、-

        • {ノードの右側、lvl+1}を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 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;
}
void tree_level_trav(TreeNode*root){
   if (root == NULL) return;
      cout << "[";
   queue<TreeNode *> q;
   TreeNode *curr;
   q.push(root);
   q.push(NULL);
   while (q.size() > 1) {
      curr = q.front();
      q.pop();
      if (curr == NULL){
         q.push(NULL);
      }
      else {
         if(curr->left)
            q.push(curr->left);
         if(curr->right)
            q.push(curr->right);
         if(curr == NULL || curr->val == 0){
            cout << "null" << ", ";
         }
         else{
            cout << curr->val << ", ";
         }
      }
   }
   cout << "]"<<endl;
}
class Solution {
public:
   TreeNode* addOneRow(TreeNode* root, int v, int d) {
      if (d == 1) {
         TreeNode* temp = new TreeNode(v);
         temp->left = root;
         root = temp;
      }
      else {
         stack<pair<TreeNode*, int> > st;
         st.push({ root, 2 });
         int lvl = 0;
         pair<TreeNode*, int> temp;
         TreeNode* node;
         while (!st.empty()) {
            temp = st.top();
            st.pop();
            lvl = temp.second;
            node = temp.first;
            if (lvl == d) {
               TreeNode* temp1 = new TreeNode(v);
               TreeNode* temp2 = new TreeNode(v);
               temp1->left = node->left;
               temp2->right = node->right;
               node->left = temp1;
               node->right = temp2;
            }
            else {
               if (node->left && node->left->val != 0) {
                  st.push({ node->left, lvl + 1 });
               }
               if (node->right && node->right->val != 0) {
                  st.push({ node->right, lvl + 1 });
               }
            }
         }
      }
      return root;
   }
};
main(){
   Solution ob;
   vector<int> v = {4,2,6,3,1,5};
   TreeNode *root = make_tree(v);
   tree_level_trav(ob.addOneRow(root, 1, 2));
}

入力

{4,2,6,3,1,5}, 1, 2

出力

[4, 1, 1, 2, 6, 3, 1, 5, ]