लेवल ऑर्डर ट्रैवर्सल (BFS) से दिए गए नोड के उसी लेवल पर दाएं पड़ोसी नोड को ढूंढें।
एल्गोरिदम
- क्यू से BFS, लेवल दर लेवल प्रोसेस करें।
- प्रत्येक लेवल के नोड्स को
tempलिस्ट में स्टोर करें। - अगर टारगेट नोड
uमिले तो उसका इंडेक्स नोट करें। - अगर इंडेक्स अंतिम है तो None रिटर्न (दाएं कोई नहीं)।
- अन्यथा
temp[index+1]रिटर्न करें।
उदाहरण कोड
from queue import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def solve(root, u):
if not root: return None
dq = deque([root])
while dq:
dq_size = len(dq)
temp = []
index = -1
for _ in range(dq_size):
node = dq.popleft()
if node.left: dq.append(node.left)
if node.right: dq.append(node.right)
temp.append(node)
if node == u:
index = len(temp) - 1
if index == len(temp) - 1: return None
if index > -1: return temp[index + 1]
return None
# टेस्ट: ट्री [5,3,7,2,4,6,8], u=6 -> दाएं नोड = 8
इनपुट/आउटपुट
इनपुट: ट्री [5,3,7,2,4,6,8], नोड u=6
आउटपुट: 8
