Python में रूट से लीफ संख्याओं का योग

समस्या

मान लीजिए हमारे पास एक बाइनरी ट्री है जिसमें केवल 0-9 के अंक हैं, यहां सभी रूट-टू-लीफ पथ एक संख्या को दर्शा सकते हैं।

उदाहरण के लिए, यदि ट्री इस तरह है:

यह दो पथ 21 और 23 को दर्शाता है, इसलिए आउटपुट 21 + 23 = 44 होगा।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

dfs() नामक एक पुनरावर्ती फ़ंक्शन बनाएं, यह रूट और num लेगा। प्रारंभ में num = 0
यदि नोड null नहीं है
- num := num * 10 + नोड का मान
- यदि नोड का दायाँ null नहीं है और नोड का बायाँ null नहीं है, तो
  - sum := sum + num
  - num := num / 10
  - फ़ंक्शन से लौटें
- dfs(नोड का दायाँ, num)
- dfs(नोड का बायाँ, num)
- num := num / 10
- विधि से लौटें
प्रारंभ में sum := 0
रूट का उपयोग करके dfs कॉल करें, और
sum लौटाएं।

उदाहरण (Python):

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

class TreeNode:    def __init__(self, data, left = None, right = None):       self.data = data       self.left = left       self.right = right def insert(temp,data):    que = []    que.append(temp)    while (len(que)):       temp = que[0]       que.pop(0)       if (not temp.left):          if data is not None:             temp.left = TreeNode(data)          else:             temp.left = TreeNode(0)          break       else:          que.append(temp.left)       if (not temp.right):          if data is not None:             temp.right = TreeNode(data)          else:             temp.right = TreeNode(0)          break       else:          que.append(temp.right) def make_tree(elements):    Tree = TreeNode(elements[0])    for element in elements[1:]:       insert(Tree, element)    return Tree class Solution(object):    def sumNumbers(self, root):       self.sum = 0       self.dfs(root)       return self.sum    def dfs(self,node,num=0):       if node:          num = num*10 + node.data          if not node.right and not node.left:             self.sum+=num             num/=10             return          self.dfs(node.right,num)          self.dfs(node.left,num)          num/=10          return ob1 = Solution() tree = make_tree([2,1,3]) print(ob1.sumNumbers(tree))

इनपुट

[2,1,3]