केवल एक ही चाइल्ड नोड वाले नोड्स की संख्या खोजें
बाइनरी ट्री का निर्माण रिकर्सिव तरीके से किया जा सकता है। मान लीजिए कि यह ट्री उपयोगकर्ता से ली गई इनपुट के आधार पर बनाया जाता है। अगर नोड मौजूद नहीं है, तो उपयोगकर्ता 0 दर्ज करता है, और अगर नोड मौजूद है, तो वह कोई धनात्मक संख्या होगा।
रूट से शुरू करते हुए, हम उपयोगकर्ता से इनपुट पढ़ते हैं और अगर संख्या धनात्मक है तो अगली उपवृक्ष की ओर बढ़ते हैं, जबकि अगर संख्या 0 है तो उसी जगह पर रुक जाते हैं (यानि उस दिशा में subtree नहीं बनता)।
vals = map(int, input().split()) # BST के मान इनपुट से पढ़ें
idx = 0 # यह वर्तमान मान का सूचक है
root = Node(vals[idx]) # रूट नोड का मान सेट करें
def read(node: Node): # वृक्ष में सभी डेटा को पुनरावृत्त तरीके से पढ़ें
if node.value == 0: # यदि वर्तमान मान 0 है => नोड मौजूद नहीं है
return # इसलिए, हम इसके बाएँ और दाएँ बच्चों को नहीं पढ़ते
node.left = Node(vals[idx + 1]) # बाएँ नोड का मान सेट करें
node.right = Node(vals[idx + 2]) # दाएँ नोड का मान सेट करें
idx += 2 # वर्तमान मान सूचक को अद्यतन करें
read(node.left) # बाएँ उपवृक्ष के डेटा के लिए अनुरोध करें
read(node.right) # दाएँ उपवृक्ष के डेटा के लिए अनुरोध करेंऊपर दिए गए उदाहरण में आप देख सकते हैं कि प्रारंभ में नोड्स की संख्या निश्चित नहीं होती। यह प्रोग्राम रूट से शुरू होकर बाएँ subtree को पूरा पढ़ता है, जहाँ तक 0 न मिले, वहाँ तक बांये में ट्री बनता जाता है। इसके बाद दाएँ subtree के लिए वही क्रम चलता है। यह प्रक्रिया तब तक चलती रहती है जब तक सभी निचले नोड्स 0 सेट नहीं हो जाते और इनपुट में कोई संख्या बची नहीं रहती। इसलिए, ऊपर चित्रित ट्री के लिए उपयोगकर्ता का इनपुट इस तरह हो सकता है:
1 # root
2 # root.left
3 # root.right
4 # root.left.left
5 # root.left.right
0 # root.left.left.left does not exist (no left child of 4)
0 # root.left.left.right does not exist (no right child of 4)
0 # root.left.right.left does not exist (no left child of 5)
0 # root.left.right.right does not exist (no right child of 5)
6 # root.right.left
7 # root.right.right
0 # root.right.left.left does not exist (no left child of 6)
0 # root.right.left.right does not exist (no right child of 6)
8 # root.right.right.left
9 # root.right.right.right
0 # root.right.right.left.left does not exist (no left child of 8)
0 # root.right.right.left.right does not exist (no right child of 8)
0 # root.right.right.right.left does not exist (no left child of 9)
0 # root.right.right.right.right does not exist (no right child of 9)इसे एक ऐरे के रूप में भी दर्शाया जा सकता है -
[1, 2, 3, 4, 5, 0, 0, 0, 0, 6, 7, 0, 0, 8, 9, 0, 0, 0, 0], जो इसी बाइनरी ट्री का प्रतिनिधित्व करता है। यहाँ, हर बार उपयोगकर्ता से एक-एक संख्या मांगने के बजाय, हम इस ऐरे पर क्रम से चलते हुए उसी तरह रिकर्सिव तरीके से ट्री का निर्माण कर सकते हैं।मान लीजिए हमारे पास एक वैध बाइनरी ट्री है। अब आपका काम है कि आप ऐसे नोड्स की गिनती करें जो केवल एक ही चाइल्ड नोड रखते हैं।
इनपुट
इनपुट में बाइनरी ट्री के नोड्स के मान स्पेस से अलग किए हुए दिए जाते हैं। मान उसी क्रम में दिए जाते हैं जैसा ऊपर वर्णित है। 0 का अर्थ है कि वह नोड मौजूद नहीं है।
आउटपुट
प्रोग्राम को उन नोड्स की संख्या प्रिंट करनी है, जिनके केवल एक ही चाइल्ड नोड है।
उदाहरण
इनपुट | आउटपुट |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 0 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 1 |
व्याख्या
- पहले उदाहरण में ट्री का कोई भी नोड ऐसा नहीं है, जिसके केवल एक ही चाइल्ड नोड हो
- दूसरे उदाहरण में सिर्फ एक ही नोड (संख्या 3 वाला) ऐसा है, जिसमें एक ही चाइल्ड नोड है
प्रो टिप 😎
आप ऊपर दिए गए कोड को इस तरह संशोधित कर सकते हैं कि यदि इनपुट में 0 न हो तो ही
node.left या node.right के लिए नोड तैयार किया जाए।Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB