मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें यूनिवैल्यू सबट्री की संख्या गिननी है। यहाँ यूनिवैल्यू सबट्री का अर्थ है कि सबट्री के सभी नोड्स का मान समान हो।
इसलिए, यदि इनपुट है root = [5,1,5,5,5,null,5],
तो आउटपुट 4 होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक फ़ंक्शन solve() परिभाषित करें, जो नोड को पैरामीटर के रूप में लेगा,
यदि नोड खाली है, तो -
true लौटाएं
left := solve(node का बायाँ भाग)
right := solve(node का दायाँ भाग)
यदि left false है या right false है, तो -
false लौटाएं
यदि node का बायाँ भाग मौजूद है और node का मान node के बाएँ भाग के मान के बराबर नहीं है, तो -
false लौटाएं
यदि node का दायाँ भाग मौजूद है और node का मान node के दाएँ भाग के मान के बराबर नहीं है, तो -
false लौटाएं
(ret को 1 से बढ़ाएं)
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; } }; 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}आउटपुट
4
