C++-এ বাইনারি ট্রিতে সিউডো-প্যালিনড্রোমিক পাথ গণনা

একটি বাইনারি ট্রি আছে যেখানে নোডের মান ১ থেকে ৯। একটি পাথ সিউডো-প্যালিনড্রোমিক যদি তার নোড ভ্যালুদের কমপক্ষে একটি পারমুটেশন প্যালিনড্রোম হয়। রুট থেকে লিফ পর্যন্ত এতো পাথ কতটুকু আছে বের করতে হবে।

প্যালিনড্রোমের শর্ত: সর্বোচ্চ একটি অযগ কাউন্ট থাকতে পারে।

ইনপুট ট্রি চিত্রে দেখানো হয়েছে → আউটপুট: 2 (পাথ: [2,3,3] ও [2,1,1])

সমাধানের ধাপগুলো (DFS + বিটমাস্ক/কাউন্ট):

ok(v) ফাংশন: অযগ কাউন্ট ০ বা ১ কিনা চেক করব
dfs(node, cnt) ফাংশন: রুট থেকে লিফ ট্রায়ভার্স করব
প্রতি নোডে cnt[val]++, লিফে ok(cnt) চেক করব
ব্যাকট্র্যাকিংয় cnt[val]--

উদাহরণ

নিচের কোডটি দেখুন −

#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;
    }
};

int 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}