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

बाइनरी ट्री में सबसे लंबे वैकल्पिक पथ की लंबाई ज्ञात करने का पायथन प्रोग्राम


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

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

बाइनरी ट्री में सबसे लंबे वैकल्पिक पथ की लंबाई ज्ञात करने का पायथन प्रोग्राम

तो आउटपुट 5 होगा क्योंकि वैकल्पिक पथ है [2, 4, 5, 7, 8]।

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

  • यदि root नल है, तो
    • 0 लौटाएं
  • एक फ़ंक्शन dfs() परिभाषित करें। यह node, count, flag लेगा
  • यदि node नल नहीं है, तो
    • यदि flag, सत्य के समान है, तो
      • a := dfs(node का बायाँ, count + 1, असत्य)
      • b := dfs(node का दायाँ, 1, सत्य)
    • अन्यथा जब flag, असत्य के समान है, तो
      • a := dfs(node का दायाँ, count + 1, सत्य)
      • b := dfs(node का बायाँ, 1, असत्य)
    • a, b में से अधिकतम लौटाएं
  • count लौटाएं
  • मुख्य विधि से निम्न करें:
  • a := dfs(root का बायाँ, 1, असत्य)
  • b := dfs(root का दायाँ, 1, सत्य)
  • a, b में से अधिकतम लौटाएं

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

उदाहरण

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):
        if not root:
            return 0
        def dfs(node, count, flag):
            if node:
                if flag == True:
                    a = dfs(node.left, count + 1, False)
                    b = dfs(node.right, 1, True)
                elif flag == False:
                    a = dfs(node.right, count + 1, True)
                    b = dfs(node.left, 1, False)
                return max(a, b)
            return count
        a = dfs(root.left, 1, False)
        b = dfs(root.right, 1, True)
        return max(a, b)

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.right = TreeNode(7)
root.right.left.right.left = TreeNode(8)
print(ob.solve(root))

इनपुट

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.right = TreeNode(7)
root.right.left.right.left = TreeNode(8)

आउटपुट

5

  1. पायथन में रूट से लीफ तक के सबसे लंबे पथ के योग को खोजने का प्रोग्राम पायथन में रूट से लीफ तक के सबसे लंबे पथ के योग को खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें रूट से लीफ नोड तक के सबसे लंबे पथ का योग ढूंढना है। यदि दो समान लंबे पथ हैं, तो बड़े योग वाले पथ को वापस करें।इसलिए, यदि इनपुट इस तरह हैतो आउटपुट 20 होगा।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −एक फ़ंक्शन rec() परिभाषित करें। यह curr लेगायदि

  1. पायथन में बाइनरी ट्री में सबसे लंबे सम-मूल्य पथ को खोजने का प्रोग्राम पायथन में बाइनरी ट्री में सबसे लंबे सम-मूल्य पथ को खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें ट्री में किन्हीं दो नोड्स के बीच केवल सम मान वाले नोड्स से बने सबसे लंबे पथ को ढूंढना है। उदाहरण के लिए, यदि इनपुट निम्न ट्री है: तो आउटपुट 5 होगा क्योंकि सबसे लंबा पथ [10, 2, 4, 8, 6] है। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे: ans := 0 आरंभ क

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

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