मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें समान बाएं और दाएं उपट्री वाले सबसे बड़े उपट्री को ढूंढना है। पसंदीदा समय जटिलता O(n) है।
तो, यदि इनपुट इस तरह है
तो आउटपुट होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
एक फ़ंक्शन solve() परिभाषित करें। यह root, encode, maxSize, maxNode लेगा
यदि root, None है, तो
0 वापस करें
left_list := एक खाली स्ट्रिंग के साथ सूची
right_list := एक खाली स्ट्रिंग के साथ सूची
ls := solve(root.left, left_list, maxSize, maxNode)
rs := solve(root.right, right_list, maxSize, maxNode)
size := ls + rs + 1
यदि left_list[0], right_list[0] के समान है, तो
यदि size > maxSize[0], तो
maxSize[0] := size
maxNode[0] := root
encode[0] := encode[0] concatenate "|" concatenate left_list[0] concatenate "|"
encode[0] := encode[0] concatenate "|" concatenate str(root.data) concatenate "|"
encode[0] := encode[0] concatenate "|" concatenate right_list[0] concatenate "|"
size वापस करें
मुख्य विधि से, निम्नलिखित करें -
maximum := [0]
encode := एक खाली स्ट्रिंग के साथ सूची
solve(node, encode, maximum, maxNode)
maximum वापस करें
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
class TreeNode: def __init__(self, data): self.data = data self.left = self.right = None def solve(root, encode, maxSize, maxNode): if (root == None): return 0 left_list = [""] right_list = [""] ls = solve(root.left, left_list, maxSize, maxNode) rs = solve(root.right, right_list, maxSize, maxNode) size = ls + rs + 1 if (left_list[0] == right_list[0]): if (size > maxSize[0]): maxSize[0] = size maxNode[0] = root encode[0] = encode[0] + "|" + left_list[0] + "|" encode[0] = encode[0] + "|" + str(root.data) + "|" encode[0] = encode[0] + "|" + right_list[0] + "|" return size def largestSubtree(node, maxNode): maximum = [0] encode = [""] solve(node, encode, maximum, maxNode) return maximum root = TreeNode(55) root.left = TreeNode(15) root.right = TreeNode(70) root.left.left = TreeNode(10) root.left.right = TreeNode(25) root.right.left = TreeNode(75) root.right.left.left = TreeNode(65) root.right.left.right = TreeNode(80) root.right.right = TreeNode(75) root.right.right.left = TreeNode(65) root.right.right.right = TreeNode(80) maxNode = [None] maximum = largestSubtree(root, maxNode) print("Root of largest sub-tree", maxNode[0].data) print("and its size is ", maximum) इनपुट
root = TreeNode(55) root.left = TreeNode(15) root.right = TreeNode(70) root.left.left = TreeNode(10) root.left.right = TreeNode(25) root.right.left = TreeNode(75) root.right.left.left = TreeNode(65) root.right.left.right = TreeNode(80) root.right.right = TreeNode(75) root.right.right.left = TreeNode(65) root.right.right.right = TreeNode(80)
आउटपुट
Root of largest sub-tree 70 and its size is [7]
