C++で汚染された二分木の要素を検索する

二分木があるとします。そのツリーのルールは次のとおりです-

• root.val ==0

• treeNode.valがxで、treeNode.leftがnullでない場合、treeNode.left.val =2 * x + 1

• treeNode.valがxで、treeNode.rightがnullでない場合、treeNode.right.val =2 * x + 2

今、二分木が汚染されているので。これは、ツリーノードのすべての値が-1に変更されたことを示します。最初にバイナリツリーを回復してから、次のようにFindElementsクラスを実装する必要があります-

• FindElements（TreeNode * root）汚染された二分木でオブジェクトを初期化します。最初にそれを回復する必要があります。

• bool find（int target）。復元されたバイナリツリーにターゲット値が存在する場合、これが返されます。

したがって、ツリーが次のような場合-

したがって、回復した後、1、3、および5を見つけようとすると、結果はtrue、true、およびfalseになります。

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

• セットを定義する

• dfs（）メソッドを定義します。これはrootを取り、rootValを取ります。 rootValは最初は-1です

• ルートがnullの場合は、

  を返します。

• rootValが-1の場合、rootの値を0に設定し、そうでない場合はrootVal

  として設定します。

• ルートの値を

  に挿入します

• dfs（ルートの左側、ルートの2*値+1）、dfs（ルートの右側、ルートの2*値+2）

  を呼び出します。

• 初期化（または再構築）のために、dfs（root、-1）

  を呼び出します。

• いくつかの要素を見つけるには、要素がaにあるかどうかを確認します。ある場合はtrueを返し、そうでない場合はfalseを返します。

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

例

#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;
}
class FindElements {
   public:
   set <int> a;
   void dfs(TreeNode* root,int rootVal=-1){
      if(!root)return;
      root->val = rootVal == -1?0:rootVal;
      a.insert(root->val);
      dfs(root->left,2*root->val + 1);
      dfs(root->right, 2*root->val + 2);
   }
   FindElements(TreeNode* root) {
      dfs(root);
   }
   bool find(int t) {
      return a.find(t)!=a.end();
   }
};
main(){
   vector<int> v = {-1,-1,-1,-1,-1};
   TreeNode *root = make_tree(v);
   FindElements ob(root);
   cout << (ob.find(1)) << endl;
   cout << (ob.find(3)) << endl;
   cout << (ob.find(5)) << endl;
}

入力

Initialize the tree with [-1,-1,-1,-1,-1], then call find(1), find(3) and find(5)

出力

1
1
0