मान लीजिए हमारे पास एक बाइनरी ट्री है जहां नोड मान 1 से 9 तक के अंक हैं। बाइनरी ट्री में एक पथ को सूडो-पैलिंड्रोमिक कहा जाता है जब पथ में नोड मानों का कम से कम एक क्रमचय एक पैलिंड्रोम होता है। हमें रूट नोड से लीफ नोड्स तक जाने वाले सूडो-पैलिंड्रोमिक पथ की संख्या ढूंढनी है।
इसलिए, यदि इनपुट है
तो आउटपुट 2 होगा, क्योंकि रूट नोड से लीफ नोड्स तक जाने वाले तीन पथ हैं - लाल पथ [2,3,3] का अनुसरण करता है, हरा पथ [2,1,1] का अनुसरण करता है, और पथ [2,3,1]। इन पथों में केवल लाल पथ और हरा पथ सूडो-पैलिंड्रोमिक हैं क्योंकि लाल पथ [2,3,3] को [3,2,3] के रूप में पुनर्व्यवस्थित किया जा सकता है और हरा पथ [2,1,1] को [1,2,1] के रूप में पुनर्व्यवस्थित किया जा सकता है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक फ़ंक्शन ok() परिभाषित करें, जो एक ऐरे v लेगा,
odd := 0
v के प्रत्येक एलिमेंट it के लिए -
odd := odd + (it AND 1)
true लौटाएं जब odd 0 हो OR odd 1 हो, अन्यथा false
एक फ़ंक्शन dfs() परिभाषित करें, जो node, ऐरे v लेगा,
यदि node null है, तो -
लौटें
v[node के मान] को 1 से बढ़ाएं
यदि node का बायाँ भाग null है और दायाँ भाग null है, तो -
यदि ok(v) true है, तो -
(ret को 1 से बढ़ाएं)
v[node के मान] को 1 से घटाएं
लौटें
dfs(node का बायाँ भाग, v)
dfs(node का दायाँ भाग, v)
v[node के मान] को 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
