पायथन में बाइनरी ट्री के पूर्ण होने की जांच करने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें जांचना है कि यह एक पूर्ण बाइनरी ट्री है या नहीं। जैसा कि हम जानते हैं एक पूर्ण बाइनरी ट्री में स्तर नोड्स से भरे होते हैं सिवाय संभवतः अंतिम स्तर के और अंतिम स्तर के सभी नोड्स जितना संभव हो उतना बाएं होते हैं।

उदाहरण के लिए, यदि इनपुट जैसा है: तो आउटपुट True होगा।

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

• q := एक डबल-एंडेड क्यू
• q के अंत में रूट डालें
• flag := असत्य
• जब तक q खाली नहीं है, करें:
  • temp := q के बाएं से हटाया गया तत्व
  • यदि temp null है, तो flag := सत्य
  • अन्यथा यदि flag सेट है और temp null नहीं है, तो असत्य वापस करें
  • अन्यथा, q के अंत में temp का बायां और दायां डालें
• सत्य वापस करें

उदाहरण

from collections import deque
class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root):
        q = deque()
        q.append(root)
        flag = False
        while q:
            temp = q.popleft()
            if not temp:
                flag = True
            elif flag and temp:
                return False
            else:
                q.append(temp.left)
                q.append(temp.right)
        return True
ob = Solution()
root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.left = TreeNode(6)
root.left.right = TreeNode(8)
print(ob.solve(root))

इनपुट

root = TreeNode(9) root.left = TreeNode(7) root.right = TreeNode(10) root.left.left = TreeNode(6) root.left.right = TreeNode(8)

आउटपुट

True