मान लीजिए हमारे पास बाइनरी ट्री है; हमें जांचना है कि बाइनरी ट्री का दिया गया वर्टिकल लेवल क्रमबद्ध है या नहीं। जब दो नोड ओवरलैप हो रहे हों, तो जांचें कि वे उस लेवल से संबंधित हैं जहां वे क्रमबद्ध क्रम में हैं।
तो, यदि इनपुट l = -1 है
तो आउटपुट True होगा, क्योंकि लेवल -1 में तत्व 3, 7 हैं और वे क्रमबद्ध हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
यदि root null है, तो
True वापस करें
previous_value := -inf
current_level := 0
current_node := मान 0 के साथ एक नया ट्री नोड
q नामक एक डीक्यू परिभाषित करें
q के अंत में (root, 0) डालें
जब q खाली नहीं है, करें
current_node := q[0, 0]
current_level := q[0, 1]
q के बाएं से तत्व हटाएं
यदि current_level, लेवल के समान है, तो
यदि previous_value <= current_node.val, तो
previous_value := current_node.val
अन्यथा,
False वापस करें
यदि current_node.left null नहीं है, तो
q के अंत में (current_node.left, current_level - 1) डालें
यदि current_node.right गैर-null है, तो
q के अंत में (current_node.right, current_level + 1) डालें
True वापस करें
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
from collections import deque from sys import maxsize INT_MIN = -maxsize class TreeNode: def __init__(self, key): self.val = key self.left = None self.right = None def are_elements_sorted(root, level): if root is None: return True previous_value = INT_MIN current_level = 0 current_node = TreeNode(0) q = deque() q.append((root, 0)) while q: current_node = q[0][0] current_level = q[0][1] q.popleft() if current_level == level: if previous_value <= current_node.val: previous_value = current_node.val else: return False if current_node.left: q.append((current_node.left, current_level - 1)) if current_node.right: q.append((current_node.right, current_level + 1)) return True root = TreeNode(2) root.left = TreeNode(3) root.right = TreeNode(6) root.left.left = TreeNode(8) root.left.right = TreeNode(5) root.left.right.left = TreeNode(7) level = -1 print(are_elements_sorted(root, level))
इनपुट
root = TreeNode(2) root.left = TreeNode(3) root.right = TreeNode(6) root.left.left = TreeNode(8) root.left.right = TreeNode(5) root.left.right.left = TreeNode(7)
आउटपुट
True
