पायथन में एक बाइनरी ट्री में दूसरा सबसे गहरा नोड खोजने का कार्यक्रम

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें दूसरी सबसे गहरी पत्ती की गहराई का पता लगाना है। यदि कई गहरे पत्ते हैं, तो दूसरा सबसे गहरा पत्ता नोड अगला उच्चतम होगा। जैसा कि हम जानते हैं कि जड़ की गहराई 0 होती है।

तो, अगर इनपुट पसंद है

तो आउटपुट 1 होगा, क्योंकि दूसरा सबसे गहरा नोड 3 है।

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

यदि रूट रिक्त है, तो
- वापसी शून्य
नोड्स:=एक नई सूची
नोड्स के अंत में रूट डालें
गिनती :=0, पिछला :=0, अब :=0
जबकि नोड्स खाली नहीं हैं, करें
- नया:=एक नई सूची
- झंडा :=सच
- नोड्स में प्रत्येक नोड के लिए, करें
  - यदि ध्वज सत्य है और (नोड का बायां भाग शून्य है) और (नोड का दायां शून्य है), तो
    - पिछला :=अब
    - अब :=गिनती
    - झंडा :=झूठा
  - यदि नोड का बायां भाग रिक्त नहीं है, तो
    - नए के अंत में नोड के बाईं ओर डालें
  - यदि नोड का अधिकार शून्य नहीं है, तो
    - नए के अंत में नोड के दाईं ओर डालें
- नोड्स :=नया
- गिनती :=गिनती + 1
पिछला वापसी

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

उदाहरण

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 root is None:
         return None
      nodes = []
      nodes.append(root)
      count = 0
      prev = 0
      now = 0
      while nodes:
         new = []
         flag = True
         for node in nodes:
         if flag and (not node.left) and (not node.right):
            prev = now
            now = count
            flag = False
         if node.left:
            new.append(node.left)
         if node.right:
            new.append(node.right)
      nodes = new
      count += 1
   return prev

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.left = TreeNode(7)
root.right.right.right = 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.left = TreeNode(7)
root.right.right.right = TreeNode(8)