पायथन में सबसे गहरे पत्तों का लोएस्ट कॉमन एन्सेस्टर

मान लीजिए हमारे पास एक रूटेड बाइनरी ट्री है, हमें इसके सबसे गहरे पत्तों का लोएस्ट कॉमन एन्सेस्टर लौटाना है। हमें ध्यान रखना होगा कि -

• बाइनरी ट्री का नोड लीफ नोड है यदि और केवल यदि इसके कोई चिल्ड्रन नहीं हैं

• ट्री के रूट की गहराई 0 है, और जब किसी नोड की गहराई d है, तो इसके प्रत्येक चिल्ड्रन की गहराई d+1 है।

• नोड्स के सेट S का लोएस्ट कॉमन एन्सेस्टर नोड A है जिसकी सबसे बड़ी गहराई है जैसे कि S में प्रत्येक नोड रूट A वाले सबट्री में है।

यदि इनपुट [1,2,3,4,5] है,

तो आउटपुट [2,4,5] होगा।

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

• solve() नामक एक मेथड परिभाषित करें, यह node लेगा, यह निम्नानुसार काम करेगा -

• यदि node मौजूद नहीं है, तो [0, None] के साथ एक लिस्ट लौटाएं

• यदि node के बाएं और दाएं सबट्री खाली हैं, तो [1, None] के साथ एक लिस्ट लौटाएं

• d1, l := solve(node का बायां), d2, r := solve(node का दायां)

• यदि d1 > d2, तो [d1 + 1, l] मानों के साथ एक लिस्ट लौटाएं

• अन्यथा जब d2 > d1, तो [d2 + 1, r] मानों के साथ एक लिस्ट लौटाएं

• [d1 + 1, node] मानों के साथ एक लिस्ट लौटाएं

• मुख्य मेथड में, हम करेंगे -

• लिस्ट := solve(root)

• लिस्ट[1] लौटाएं

उदाहरण (पायथन)

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

class TreeNode:
    def __init__(self, data, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right

def insert(temp,data):
    que = []
    que.append(temp)
    while (len(que)):
        temp = que[0]
        que.pop(0)
        if (not temp.left):
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

def print_tree(root):
    # इनऑर्डर ट्रैवर्सल का उपयोग करके प्रिंट करें
    if root is not None:
        print_tree(root.left)
        print(root.data, end = ', ')
        print_tree(root.right)

class Solution(object):
    def lcaDeepestLeaves(self, root):
        return self.solve(root)[1]
    def solve(self,node):
        if not node:
            return [0,None]
        if not node.left and not node.right:
            return [1,node]
        d1,l = self.solve(node.left)
        d2,r = self.solve(node.right)
        if d1>d2:
            return [d1+1,l]
        elif d2>d1:
            return [d2+1,r]
        return [d1+1,node]

ob = Solution()
root = make_tree([1,2,3,4,5])
print_tree(ob.lcaDeepestLeaves(root))

इनपुट

[1,2,3,4,5]

आउटपुट

4, 2, 5,