मान लीजिए हमारे पास एक पूर्ण बाइनरी ट्री है, हमें नोड्स की संख्या गिननी है। तो यदि ट्री इस तरह है −
तो आउटपुट 6 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे
- यह रिकर्सिव दृष्टिकोण का उपयोग करेगा। यह मेथड, countNodes() रूट को आर्गुमेंट के रूप में ले रहा है।
- hr := 0 और hl := 0
- दो नोड्स l और r को रूट के रूप में बनाएं
- जब तक l खाली नहीं है
- hl को 1 से बढ़ाएं
- l := l का लेफ्ट
- जब तक r खाली नहीं है
- r := r का राइट
- hr को 1 से बढ़ाएं
- यदि hl = hr, तो (2 ^ hl) – 1 लौटाएं
- 1 + countNodes(रूट का लेफ्ट) + countNodes(रूट का राइट) लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
उदाहरण
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = 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 fastPow(int base, int power){ int res = 1; while(power > 0){ if(power & 1) res *= base; base *= base; power >>= 1; } return res; } int countNodes(TreeNode* root) { int hr = 0; int hl = 0; TreeNode* l = root; TreeNode* r = root; while(l){ hl++; l = l->left; } while(r){ r = r->right; hr++; } if(hl == hr) return fastPow(2, hl) - 1; return 1 + countNodes(root->left) + countNodes(root->right); } }; main(){ Solution ob; vector<int> v = {1,2,3,4,5,6,7,8,9,10}; TreeNode *node = make_tree(v); cout << (ob.countNodes(node)); }इनपुट
[1,2,3,4,5,6,7,8,9,10]
आउटपुट
10
