पायथन में बाइनरी ट्री का व्यास

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें ट्री के व्यास की लंबाई की गणना करनी है। बाइनरी ट्री का व्यास वास्तव में ट्री में किन्हीं दो नोड्स के बीच सबसे लंबे पथ की लंबाई है। यह पथ अनिवार्य रूप से रूट से होकर नहीं जाता। यदि ट्री नीचे जैसा है, तो व्यास 3 होगा क्योंकि पथ [4,2,1,3] या [5,2,1,3] की लंबाई 3 है।

हल करने के चरण

• हम व्यास ढूंढने के लिए dfs का उपयोग करेंगे, answer := 0 सेट करें
• रूट के साथ dfs फंक्शन कॉल करें dfs(root)
• dfs इस तरह काम करेगा dfs(node)
• यदि नोड मौजूद नहीं है, तो 0 वापस करें
• left := dfs(रूट का बायां सबट्री), और right := dfs(रूट का दायां सबट्री)
• answer := answer और left + right का अधिकतम
• left + 1 और right + 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):
            temp.left = TreeNode(data)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            temp.right = TreeNode(data)
            break
        else:
            que.append(temp.right)

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

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.ans = 0
        self.dfs(root)
        return self.ans

    def dfs(self, node):
        if not node:
            return 0
        left = self.dfs(node.left)
        right = self.dfs(node.right)
        self.ans =max(self.ans,right+left)
        return max(left+1,right+1)

root = make_tree([1,2,3,4,5])
ob1 = Solution()
print(ob1.diameterOfBinaryTree(root))

इनपुट

[1,2,3,4,5]

आउटपुट

3