मान लीजिए हमारे पास दो बाइनरी ट्री हैं। हमें यह जांचना है कि दूसरा ट्री पहले का सबट्री है या नहीं।
तो, यदि इनपुट इस तरह है
तो आउटपुट True होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- solve() फ़ंक्शन परिभाषित करें। यह root, target लेगा
- यदि root null है और target भी null है, तो True लौटाएं
- यदि root null है या target null है, तो False लौटाएं
- यदि root का मान target के मान के समान है, तो solve(root के बाएं, target के बाएं) और solve(root के दाएं, target के दाएं) लौटाएं
- अन्यथा, solve(root के बाएं, target) या solve(root के दाएं, target) लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
class Solution:
def solve(self, root, target):
if root == None and target == None:
return True
if root == None or target == None:
return False
if root.val == target.val:
return self.solve(root.left, target.left) and self.solve(root.right, target.right)
else:
return self.solve(root.left, target) or self.solve(root.right, target)
ob = Solution()
root1 = TreeNode(6)
root1.left = TreeNode(4)
root1.right = TreeNode(10)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)
root2 = TreeNode(4)
root2.left = TreeNode(3)
root2.right = TreeNode(5)
print(ob.solve(root1, root2))
इनपुट
root1 = TreeNode(6)
root1.left = TreeNode(4)
root1.right = TreeNode(10)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)
root2 = TreeNode(4)
root2.left = TreeNode(3)
root2.right = TreeNode(5)आउटपुट
True
