C++で二分木の指定した深さに新しい行（ノード）を追加する方法

二分木と値 v、深さ d が与えられたとき、指定された深さ d の位置に値 v を持つノードからなる新しい行を追加する必要があります。ここで、ルートノードは深さ 1 とします。この操作を行う際には、以下のルールに従います。

操作のルール

深さ d-1 に存在するすべての有効なツリーノード N に対して、値 v を持つ 2 つの新しいノードを作成し、それぞれ N の左部分木のルートおよび右部分木のルートとして配置します。その際、N の元の左部分木は新しい左側ノードの左部分木へ、元の右部分木は新しい右側ノードの右部分木へと移動します。

また、深さ d が 1 の場合、つまり深さ d-1 が存在しないときは、値 v を持つ新しいノードを作成して元のツリー全体の新しいルートとし、元のツリーはその新しいルートの左部分木として接続します。

具体例

例えば、入力が以下のような二分木だったとします。

このとき、値 1 を深さ 2 に追加すると、出力は次のようになります。

解決のためのアルゴリズム

この問題を解決するために、以下の手順を実行します。

• d が 1 と等しい場合：

  • temp ＝ 値 v を持つ新しいノードを作成

  • temp の左の子 ＝ root

  • root ＝ temp

• それ以外の場合：

  • ペア（ノードとレベル）を格納するスタック st を定義する

  • {root, 2} を st に挿入する

  • lvl ＝ 0 と初期化する

  • ペア型の変数 temp を定義する

  • st が空でない限り、以下を繰り返す：

    • temp ＝ st の先頭要素

    • st から要素を取り出す

    • lvl ＝ temp の 2 番目の要素（レベル）

    • node ＝ temp の 1 番目の要素（ノード）

    • lvl が d と等しい場合：

      • temp1 ＝ 値 v を持つ新しいノードを作成

      • temp2 ＝ 値 v を持つ新しいノードを作成

      • temp1 の左の子 ＝ node の左の子

      • temp2 の右の子 ＝ node の右の子

      • node の左の子 ＝ temp1

      • node の右の子 ＝ temp2

    • それ以外の場合：

      • node の左の子が有効なら、{node の左の子, lvl + 1} を st に挿入する

      • node の右の子が有効なら、{node の右の子, lvl + 1} を st に挿入する

• root を返す

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 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]

このように、スタックを用いて各ノードの深さを追跡しながら処理を進めることで、指定した深さに効率よく新しい行を挿入することができます。深さ d が 1 のケース（ルートの置き換え）と、それ以外のケース（d-1 層のノードの子として新ノードを挿入）を適切に区別することが、この問題のポイントです。