मान लीजिए हमारे पास पूर्णांकों की एक सूची है जो गहराई 5 से कम वाले बाइनरी ट्री को दर्शाती है। यदि ट्री की गहराई 5 से कम है, तो इस ट्री को तीन अंकों वाले पूर्णांकों की सूची द्वारा दर्शाया जा सकता है। इस सूची में प्रत्येक पूर्णांक के लिए:
- सैकड़ों अंक इस नोड की गहराई D को दर्शाता है, 1 <= D <= 4।
- दहाई अंक इस नोड की स्थिति P को उस स्तर में दर्शाता है जिसका वह संबंध रखता है, सीमा 1 से 8। स्थिति पूर्ण बाइनरी ट्री के समान है।
- इकाई अंक इस नोड के मान V को दर्शाता है, 0 <= V <= 9।
हमें रूट से पत्तियों तक सभी पथों का योग ज्ञात करना है।
उदाहरण के लिए, यदि इनपुट [113, 215, 221] है, तो आउटपुट 12 होगा। ट्री जो सूची दर्शाती है:
पथ योग (3 + 5) + (3 + 1) = 12 है।
हल करने की विधि
हम एक मैप का उपयोग करके ट्री का निर्माण करेंगे और फिर DFS करेंगे:
- स्तर के अनुसार नोड्स संग्रहीत करने के लिए एक मैप graph परिभाषित करें।
dfs()फ़ंक्शन नोड, स्तर, स्थिति, और वर्तमान योग लेता है।- अगले स्तर के बच्चों की जांच करें जिनकी स्थिति वर्तमान स्थिति के आधे के बराबर है।
- यदि लीफ नोड है, तो योग को परिणाम में जोड़ें।
- मुख्य विधि में:
- प्रत्येक संख्या को पार्स करें: मान, स्थिति, स्तर निकालें।
- graph[स्तर] में (स्थिति, मान) जोड़ें।
- रूट से dfs शुरू करें।
- परिणाम लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class Solution { public: int ret; map <int, vector < pair <int, int> > > graph; void dfs(int node, int level, int pos, int sum = 0){ bool isLeaf = true; for (int i = 0; i < graph[level + 1].size(); i++) { pair<int, int> temp = graph[level + 1][i]; if (temp.first / 2 == pos) { isLeaf = false; dfs(temp.second, level + 1, temp.first, sum + node); } } if (isLeaf) { ret += (sum + node); } } int pathSum(vector<int>& nums) { ret = 0; for (int i = 0; i < nums.size(); i++) { int x = nums[i]; int val = x % 10; x /= 10; int pos = x % 10; x /= 10; int level = x; graph[level].push_back({ (1 << (level - 1)) + pos - 1, val }); } dfs(graph[1][0].second, 1, graph[1][0].first); return ret; } }; main(){ Solution ob; vector<int> v = {113,215,221}; cout<<(ob.pathSum(v)); }
इनपुट
{113,215,221}
आउटपुट
12
