পাইথনে রুট টু ليف পাথের সংখ্যা যোগফল

ধরা যাক একটি বাইনারি ট্রি আছে যাতে শুধু 0-9 এর ডিজিটগুলো থাকে। এখানে সব রুট-টু-ليف পাথ একটি সংখ্যা রিপ্রেজেন্ট করতে পারে।

তাই যদি ট্রি হয়:

এটি দুইটি পাথ 21 এবং 23 রিপ্রেজেন্ট করছে, সুতরাং আউটপুট হবে 21 + 23 = 44।

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:

dfs() নামে একটি রিকারসিভ ফাংশন তৈরি করুন, এটি root এবং num নেবে। প্রাথমিকভাবে num = 0
যদি নোড null না হয়
- num := num * 10 + নোডের মান
- যদি নোডের রাইট null না হয় এবং নোডের লেফট null না হয়, তবে
  - sum := sum + num
  - num := num / 10
  - ফাংশন থেকে রিটার্ন করুন
- dfs(নোডের রাইট, num)
- dfs(নোডের লেফট, num)
- num := num / 10
- মেথড থেকে রিটার্ন করুন
প্রাথমিকভাবে sum := 0
root এবং num দিয়ে dfs কল করুন
sum রিটার্ন করুন।

উদাহরণ (পাইথন):

নিচের ইমপ্লিমেন্টেশনটি দেখে আরও ভালো বুঝতে পারবেন:

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]