पायथन में बाइनरी ट्री की अधिकतम चौड़ाई खोजने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें ट्री में किसी भी स्तर की अधिकतम चौड़ाई ढूंढनी है। यहां एक स्तर की चौड़ाई उन नोड्स की संख्या है जो बाएं सबसे नोड और दाएं सबसे नोड के बीच रखे जा सकते हैं।

उदाहरण के लिए, यदि इनपुट है:

तो आउटपुट होगा 2।

हल करने के चरण

एक मैप d बनाएं, न्यूनतम और अधिकतम मान रखने के लिए, न्यूनतम प्रारंभ में अनंत और अधिकतम 0।
एक फ़ंक्शन dfs() परिभाषित करें। यह root, pos := 0, depth := 0 लेगा।
यदि root नल है, तो लौटें।
d[depth][0] = min(d[depth][0], pos)
d[depth][1] = max(d[depth][1], pos)
dfs(node.left, 2*pos, depth+1)
dfs(node.right, 2*pos+1, depth+1)
मुख्य विधि से:
- dfs(root)
- mx := 0
- d के सभी मानों की सूची में प्रत्येक मिन-मैक्स जोड़े के लिए:
  - left := min, right := max
  - mx := max(mx, right - left + 1)
- mx लौटाएं।

उदाहरण

from collections import defaultdict
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):
        d = defaultdict(lambda: [1e9, 0])
        def dfs(node, pos=0, depth=0):
            if not node:
                return
            d[depth][0] = min(d[depth][0], pos)
            d[depth][1] = max(d[depth][1], pos)
            dfs(node.left, 2*pos, depth+1)
            dfs(node.right, 2*pos+1, depth+1)
        dfs(root)
        mx = 0
        for interval in d.values():
            l, r = interval
            mx = max(mx, r - l + 1)
        return mx

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

इनपुट

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