C++の二分木における疑似パリンドロームパス

ノード値が1から9までの数字であるバイナリツリーがあるとします。パス内のノード値の少なくとも1つの順列が回文である場合、バイナリツリーの1つのパスは疑似回文であると言われます。ルートノードからリーフノードに向かう疑似パリンドロームパスの数を見つける必要があります。

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

その場合、出力は2になります。これは、ルートノードからリーフノードに向かう3つのパスがあるためです。赤いパスは[2,3,3]に従い、緑のパスは[2,1,1]に従い、パス[ 2,3,1]。これらのパスのうち、赤のパス[2,3,3]は[3,2,3]として再配置でき、緑のパス[2,1,1]は再配置できるため、赤のパスと緑のパスのみが疑似パリンドロームパスです。 [1,2,1]として。

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

• 関数ok（）を定義します。これは配列vを取ります

• 奇数：=0

• 各要素について、v −

  • 奇数：=奇数+それと1

• 奇数が0または奇数が1の場合はtrueを返し、それ以外の場合はfalseを返します

• 関数dfs（）を定義します。これは、ノード、配列v、

  を取ります。

• ノードがnullの場合、-

  • 戻る

• v[ノードの値]を1増やします

• ノードの左側がnullで、ノードの右側がnullの場合、-

  • ok（v）が真の場合、-

    • （retを1増やします）

  • v[ノードの値]を1つ減らします

  • 戻る

• dfs（ノードの左側、v）

• dfs（ノードの右側、v）

• v[ノードの値]を1つ減らします

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

• ret：=0

• サイズ10の配列cntを定義します

• dfs（root、cnt）

• retを返す

例

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

#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 Solution {
public:
   int ret;
   bool ok(vector <int>& v){
      int odd = 0;
      for (auto& it : v) {
         odd += it & 1;
      }
      return odd == 0 || odd == 1;
   }
   void dfs(TreeNode* node, vector <int>& v){
      if (!node)
         return;
      v[node->val]++;
      if (!node->left && !node->right) {
         if (ok(v))
            ret++;
         v[node->val]--;
         return;
      }
      dfs(node->left, v);
      dfs(node->right, v);
      v[node->val]--;
   }
   int pseudoPalindromicPaths (TreeNode* root) {
      ret = 0;
      vector<int> cnt(10);
      dfs(root, cnt);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,3,1,3,1,NULL,1};
   TreeNode *root = make_tree(v);
   cout << (ob.pseudoPalindromicPaths(root));
}

入力

{2,3,1,3,1,NULL,1}

出力

2