C++-এ ইউনিভ্যালু সাবট্রি গণনা

আমাদের একটি বাইনারি ট্রি দেওয়া আছে; আমাদেরকে ইউনি-ভ্যালু সাবট্রিগুলোর সংখ্যা গণনা করতে হবে। এখানে ইউনি-ভ্যালু সাবট্রি বলতে একটি সাবট্রির সব নোডের মান একই থাকাকে বোঝায়।

যেমন, ইনপুট হলে root = [5,1,5,5,5,null,5],

তবে আউটপুট হবে 4

এটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:

solve() ফাংশন ডিফাইন করব, যা নোড নেবে প্যারামিটার হিসেবে,
যদি নোড খালি হয়, তবে −
- true রিটার্ন করব
left := solve(node->left)
right := solve(node->right)
যদি left বা right false হয়, তবে −
- false রিটার্ন করব
যদি বাম নোড থাকে এবং বর্তমান নোডের মান বাম নোডের মানের সমান না হয়, তবে −
- false রিটার্ন করব
যদি ডান নোড থাকে এবং বর্তমান নোডের মান ডান নোডের মানের সমান না হয়, তবে −
- false রিটার্ন করব
ret এক বেড়াব (গণনা বাড়াবে)
true রিটার্ন করব
মেইন মেথড থেকে নিচের কাজগুলো করব −
ret := 0
solve(root) কল করব
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 solve(TreeNode* node) {
        if (!node || node->val == 0)
            return true;
        bool left = solve(node->left);
        bool right = solve(node->right);
        if (!left || !right)
            return false;
        if (node->left && node->left->val != 0 && node->val != node->left->val)
            return false;
        if (node->right && node->right->val != 0 && node->val != node->right->val)
            return false;
        ret++;
        return true;
    }
    int countUnivalSubtrees(TreeNode* root) {
        ret = 0;
        solve(root);
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {5,1,5,5,5,NULL,5};
    TreeNode *root = make_tree(v);
    cout << (ob.countUnivalSubtrees(root));
}

ইনপুট

{5,1,5,5,5,NULL,5}