मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें ट्री में किसी भी स्तर की अधिकतम चौड़ाई ढूंढनी है। यहां एक स्तर की चौड़ाई उन नोड्स की संख्या है जो बाएं-most नोड और दाएं-most नोड के बीच रह सकते हैं।
उदाहरण के लिए, यदि इनपुट है
तो आउटपुट होगा 2
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- एक मैप d बनाएं, न्यूनतम और अधिकतम मान रखने के लिए, न्यूनतम प्रारंभ में अनंत है और अधिकतम 0 है
- एक फ़ंक्शन dfs() परिभाषित करें। यह root, pos := 0, depth := 0 लेगा
- यदि root null है, तो वापस करें
- d[depth, 0] = d[depth,0] और pos का न्यूनतम
- d[depth, 1] = d[depth,1] और pos का अधिकतम
- dfs(नोड का बायां, 2*pos, depth+1)
- dfs(नोड का दायां, 2*pos+1, depth+1)
- मुख्य विधि से, निम्नलिखित करें:
- dfs(root)
- mx := 0
- d के सभी मानों की सूची में प्रत्येक मिन-मैक्स जोड़े के लिए, करें
- left := min, right := max
- mx := 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)
आउटपुट
2
