मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें यह जांचना है कि ट्री सममित ट्री है या नहीं। एक ट्री को सममित कहा जाएगा यदि यह उसके दर्पण छवि लेने पर समान हो। इन दो ट्री में से पहला सममित है, लेकिन दूसरा नहीं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे।
- हम निम्नलिखित चरणों को रिकर्सिवली कॉल करेंगे। फ़ंक्शन solve(root, root) होगा
- यदि node1 और node2 खाली हैं, तो True लौटाएं
- यदि node1 या node2 में से कोई खाली है, तो False लौटाएं
- True लौटाएं जब node1.val = node2.val और solve(node1.left, node2.right) और solve(node1.right, node2.left)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
class Solution(object):
def isSymmetric(self, root):
return self.solve(root, root)
def solve(self, node1, node2):
if not node1 and not node2:
return True
if not node1 or not node2:
return False
return node1.data == node2.data and self.solve(node1.left, node2.right) and self.solve(node1.right, node2.left)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)
ob1 = Solution()
print(ob1.isSymmetric(root))
इनपुट
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)आउटपुट
True
