पायथन में दिए गए बाइनरी ट्री में सबसे बड़ा परफेक्ट सबट्री खोजें

मान लीजिए हमारे पास एक दिया गया बाइनरी ट्री है; हमें उस दिए गए बाइनरी ट्री में सबसे बड़े परफेक्ट सब-ट्री का आकार ढूंढना है। जैसा कि हम जानते हैं, परफेक्ट बाइनरी ट्री एक बाइनरी ट्री है जिसमें सभी आंतरिक नोड्स के दो बच्चे होते हैं और सभी पत्ते समान स्तर पर होते हैं।

तो, यदि इनपुट इस तरह है:

तो आउटपुट 3 होगा, और सबट्री है:

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

• RetType नामक एक ब्लॉक परिभाषित करें, यह isPerfect, height और rootTree धारण करेगा, वे सभी प्रारंभ में 0 हैं

• get_perfect_subtree() नामक एक फंक्शन परिभाषित करें, यह root लेता है

• r_type := एक नया RetType

• यदि root, None के समान है, तो:

  • r_type.isPerfect := True

  • r_type.height := 0

  • r_type.rootTree := null

  • r_type लौटाएं

• left_subtree := get_perfect_subtree(root.left)

• right_subtree := get_perfect_subtree(root.right)

• यदि left_subtree परफेक्ट है और right_subtree परफेक्ट है और left_subtree की ऊंचाई, right_subtree की ऊंचाई के समान है, तो:

  • r_type की ऊंचाई := left_subtree की ऊंचाई + 1

  • r_type को परफेक्ट सेट करें

  • r_type.rootTree := root

  • r_type लौटाएं

• r_type को परफेक्ट नहीं सेट करें

• r_type.height := left_subtree की ऊंचाई और right_subtree की ऊंचाई का अधिकतम

• यदि left_subtree की ऊंचाई > right_subtree की ऊंचाई, तो:

  • r_type.rootTree := left_subtree.rootTree

• अन्यथा,

  • r_type.rootTree := right_subtree.rootTree

• r_type लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

class TreeNode:    def __init__(self, data, left = None, right = None):       self.data = data       self.left = left       self.right = right def print_tree(root):    if root is not None:       print_tree(root.left)       print(root.data, end = ', ')       print_tree(root.right) class RetType:    def __init__(self):       isPerfect = 0       height = 0       rootTree = 0 def get_prefect_subtree(root):    r_type = RetType()    if (root == None) :       r_type.isPerfect = True       r_type.height = 0       r_type.rootTree = None       return r_type    left_subtree = get_prefect_subtree(root.left)    right_subtree = get_prefect_subtree(root.right)    if (left_subtree.isPerfect and right_subtree.isPerfect and left_subtree.height == right_subtree.height) :       r_type.height = left_subtree.height + 1       r_type.isPerfect = True       r_type.rootTree = root       return r_type    r_type.isPerfect = False    r_type.height = max(left_subtree.height, right_subtree.height)    if (left_subtree.height > right_subtree.height ):       r_type.rootTree = left_subtree.rootTree    else :       r_type.rootTree = right_subtree.rootTree    return r_type root = TreeNode(2) root.left = TreeNode(3) root.right = TreeNode(4) root.left.left = TreeNode(5) root.left.right = TreeNode(6) root.right.left = TreeNode(7) res = get_prefect_subtree(root) h = res.height print ("Size: " , pow(2, h) - 1) print ("Tree: ", end = " ") print_tree(res.rootTree)

इनपुट

root = TreeNode(2) root.left = TreeNode(3) root.right = TreeNode(4) root.left.left = TreeNode(5) root.left.right = TreeNode(6) root.right.left = TreeNode(7)

आउटपुट

Size: 3 Tree: 5, 3, 6,