मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें यह जांचना है कि ट्री में पत्तियों को छोड़कर हर नोड के लिए, उसका मान उसके बाएं बच्चे के मान और उसके दाएं बच्चे के मान के योग के समान है या नहीं।
तो, यदि इनपुट इस तरह है
तो आउटपुट True होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- dfs() फ़ंक्शन परिभाषित करें। यह root लेगा
- यदि root null है, तो True लौटाएं
- यदि root का बाएं null है और root का दाएं null है, तो True लौटाएं
- left := 0
- यदि root का बाएं null नहीं है, तो left := root के बाएं का मान
- right := 0
- यदि root का दाएं null नहीं है, तो right := root के दाएं का मान
- True लौटाएं जब (left + right, root के मान के समान हो) और dfs(root का बाएं) True हो और dfs(root का दाएं) True हो
- मुख्य मेथड से निम्नलिखित करें:
- dfs(root) लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
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):
def dfs(root):
if root == None:
return True
if root.left == None and root.right == None:
return True
left = 0
if root.left:
left = root.left.val
right = 0
if root.right:
right = root.right.val
return (left + right == root.val) and dfs(root.left) and dfs(root.right)
return dfs(root)
ob = Solution()
root = TreeNode(18)
root.left = TreeNode(8)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
print(ob.solve(root))
इनपुट
root = TreeNode(18)
root.left = TreeNode(8)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)आउटपुट
True
