Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में बाइनरी ट्री पर k-लंबाई के पथ खोजने का प्रोग्राम


मान लीजिए हमारे पास एक बाइनरी ट्री है जिसमें अद्वितीय मान हैं और हमारे पास एक अन्य मान k है, हमें ट्री में k-लंबाई के अद्वितीय पथों की संख्या ढूंढनी है। पथ पैरेंट से चाइल्ड या चाइल्ड से पैरेंट की ओर जा सकते हैं। हम दो पथों को अलग मानेंगे जब कोई नोड एक पथ में दिखाई देता है लेकिन दूसरे में नहीं।

उदाहरण के लिए, यदि इनपुट जैसा है: पायथन में बाइनरी ट्री पर k-लंबाई के पथ खोजने का प्रोग्राम k = 3, तो आउटपुट 4 होगा, क्योंकि पथ हैं [12,8,3], [12,8,10], [8,12,15], [3,8,10]।

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

  • dfs() फंक्शन परिभाषित करें जो node लेता है:
    • यदि node null है, तो 1 और k-1 शून्यों वाली सूची वापस करें
    • left := dfs(node का बायां)
    • right := dfs(node का दायां)
    • i को 0 से K तक के लिए करें:
      • ans := ans + left[i] * right[K-1-i]
    • res := आकार K की शून्यों वाली सूची
    • res[0] := 1, res[1] := 1
    • i को 1 से K-1 तक के लिए करें:
      • res[i+1] := res[i+1] + left[i]
      • res[i+1] := res[i+1] + right[i]
    • res वापस करें
  • मुख्य विधि से:
    • ans := 0
    • dfs(root)
    • ans वापस करें

उदाहरण

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, K):
        def dfs(node):
            if not node:
                return [1] + [0] * (K-1)
            left = dfs(node.left)
            right = dfs(node.right)
            for i in range(K):
                self.ans += left[i] * right[K - 1 - i]
            res = [0] * K
            res[0] = res[1] = 1
            for i in range(1, K-1):
                res[i+1] += left[i]
                res[i+1] += right[i]
            return res
        self.ans = 0
        dfs(root)
        return self.ans

ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root, 3))

इनपुट

root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10) 3

आउटपुट

4
  1. पायथन में बाइनरी ट्री के किसी भी पथ का सबसे बड़ा योग खोजने का प्रोग्राम पायथन में बाइनरी ट्री के किसी भी पथ का सबसे बड़ा योग खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें रूट नोड से लीफ नोड तक जाने वाले किसी भी पथ का सबसे बड़ा योग ढूंढना है। उदाहरण के लिए, यदि इनपुट जैसा है: तो आउटपुट 29 होगा क्योंकि रूट से, यदि हम पथ 5-<9-<7-<8 का पालन करते हैं तो जोड़ के बाद यह 29 होगा। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

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

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

  1. पायथन में बाइनरी ट्री का लोएस्ट कॉमन एंसेस्टर पायथन में बाइनरी ट्री का लोएस्ट कॉमन एंसेस्टर

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें दो दिए गए नोड्स का लोएस्ट कॉमन एंसेस्टर नोड ढूंढना है। दो नोड्स p और q का LCA वास्तव में ट्री में सबसे निचला नोड है जिसमें p और q दोनों डिसेंडेंट के रूप में हों। इसलिए यदि बाइनरी ट्री [3,5,1,6,2,0,8,null,null,7,4] जैसा है। ट्री इस तरह होगा - यहां 5 और 1 क