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

तो आउटपुट 1 होगा, क्योंकि दूसरा सबसे गहरा नोड 3 है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- यदि root नल है, तो
- नल लौटाएं
- nodes := एक नई सूची
- root को nodes के अंत में डालें
- count := 0, prev := 0, now := 0
- जब तक nodes खाली नहीं है, करें
- new := एक नई सूची
- flag := सत्य
- प्रत्येक node के लिए nodes में, करें
- यदि flag सत्य है और (node का बायाँ नल है) और (node का दायाँ नल है), तो
- prev := now
- now := count
- flag := असत्य
- यदि node का बायाँ नल नहीं है, तो
- node के बाएँ को new के अंत में डालें
- यदि node का दायाँ नल नहीं है, तो
- node के दाएँ को new के अंत में डालें
- यदि flag सत्य है और (node का बायाँ नल है) और (node का दायाँ नल है), तो
- nodes := new
- count := count + 1
- prev लौटाएं
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
उदाहरण
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)
आउटपुट
1