หาโหนดที่อยู่ทางขวา (right neighbor) ในระดับเดียวกันของโหนด u ใน binary tree ใช้ BFS ระดับต่อระดับ (level order) เก็บโหนดแต่ละระดับใน list ตรวจสอบ index ของ u แล้วคืนโหนดถัดไป ถ้าอยู่ปลายสุดคืน None
ขั้นตอนการทำงาน
- BFS ด้วย deque เก็บโหนดแต่ละระดับใน temp list
- ระหว่างวนลูประดับ ถ้าเจอ u บันทึก index
- จบระดับ: ถ้า index เป็นตัวสุดท้าย -> None, ถ้า index >= 0 -> คืน temp[index+1]
- ถ้าไม่เจอ u ในระดับนี้ ไประดับถัดไป
ตัวอย่างโค้ด
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 make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def search_node(root, element):
if root is None: return None
if root.val == element: return root
res1 = search_node(root.left, element)
if res1: return res1
return search_node(root.right, element)
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
root = make_tree([5, 3, 7, 2, 4, 6, 8])
u = search_node(root, 6)
print(solve(root, u).val) # Output: 8
อินพุต/เอาต์พุต
Input: tree, u=6 Output: 8
