একটি বাইনারি ট্রি এবং একটি টার্গেট সম দেওয়া থাকে। রুট থেকে লিফ পর্যন্ত এমন একটি পাথ আছে কিনা যাতে নোড ভ্যালুগুলোর যোগফল টার্গেটের সমান হয়। উদাহরণ: ট্রি [0,-3,9,-10,null,5], টার্গেট ১৪ → পাথ 0 → 9 → 5।
সমাধানের পদ্ধতি
- যদি রুট নাল হয়,
False। - যদি লিফ নোড হয়, চেক করুন
sum - root.val == 0। - রিকারসিভলি বাম ও ডান সাবট্রিতে
sum - root.valদিয়ে কল করুন।
উদাহরণ কোড
class TreeNode(object):
def __init__(self, x):
self.data = x
self.left = None
self.right = None
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 hasPathSum(self, root, sum):
if not root:
return False
if not root.left and not root.right and root.data is not None:
return sum - root.data == 0
if root.data is not None:
return self.hasPathSum(root.left, sum - root.data) or self.hasPathSum(root.right, sum - root.data)
tree1 = make_tree([0,-3,9,-10,None,5])
ob1 = Solution()
print(ob1.hasPathSum(tree1, 14))
ইনপুট
tree1 = make_tree([0,-3,9,-10,None,5])
আউটপুট
True
