सी ++ में एक बाइनरी ट्री में छद्म-पैलिंड्रोमिक पथ

मान लीजिए कि हमारे पास एक बाइनरी ट्री है जहां नोड मान 1 से 9 तक के अंक हैं। बाइनरी ट्री में एक पथ को छद्म-पैलिंड्रोमिक कहा जाता है, जब पथ में नोड मानों का कम से कम एक क्रमपरिवर्तन एक पैलिंड्रोम होता है। हमें रूट नोड से लीफ नोड्स तक जाने वाले छद्म-पैलिंड्रोमिक पथों की संख्या ज्ञात करनी होगी।

तो, अगर इनपुट पसंद है

तब आउटपुट 2 होगा, ऐसा इसलिए है क्योंकि रूट नोड से लीफ नोड्स तक जाने वाले तीन रास्ते हैं - लाल पथ इस प्रकार है [2,3,3], हरा पथ [2,1,1] का अनुसरण करता है, और पथ [ 2,3,1]। इन पथों में से केवल लाल पथ और हरा पथ छद्म-पैलिंड्रोमिक पथ हैं क्योंकि लाल पथ [2,3,3] को [3,2,3] के रूप में पुनर्व्यवस्थित किया जा सकता है और हरे पथ [2,1,1] को पुनर्व्यवस्थित किया जा सकता है। [1,2,1] के रूप में।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें ठीक (), यह एक सरणी v लेगा,

• विषम :=0

• v −

  . में प्रत्येक तत्व के लिए

  • विषम :=विषम + यह और 1

• जब विषम 0 हो या विषम 1 हो, तो सही लौटें, अन्यथा असत्य

• फ़ंक्शन dfs() को परिभाषित करें, यह नोड, सरणी v,

  take लेगा

• यदि नोड शून्य है, तो -

  • वापसी

• v[नोड के मान] को 1 से बढ़ाएं

• यदि नोड का बायां भाग शून्य है और नोड का दायां शून्य है, तो -

  • यदि ठीक (v) सत्य है, तो -

    • (रिटर्न 1 से बढ़ाएं)

  • v[नोड का मान] 1 से घटाएं

  • वापसी

• dfs (नोड के बाएं, v)

• dfs (नोड का दायां, v)

• v[नोड का मान] 1 से घटाएं

• मुख्य विधि से, निम्न कार्य करें -

• रिट:=0

• आकार 10

  . की एक सरणी cnt परिभाषित करें

• डीएफएस (रूट, सीएनटी)

• वापसी रिट

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#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