Python을 사용하여 이진 트리에서 오른쪽 노드를 찾는 프로그램

<시간/>

이진 트리가 제공된다고 가정합니다. 우리는 또한 노드에 대한 포인터('u'로 명명됨)를 받았고 제공된 노드의 바로 오른쪽에 위치한 노드를 찾아야 합니다. 주어진 노드의 오른쪽에 위치한 노드는 동일한 레벨에 있어야 하며 주어진 노드는 리프 노드 또는 내부 노드가 될 수 있습니다.

따라서 입력이 다음과 같으면

u =6이면 출력은 8이 됩니다.

노드 6의 오른쪽에 있는 노드는 노드 8이므로 값 8이 반환됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

루트가 비어 있으면
- null 반환
dq :=새로운 데크
dq의 끝에 루트 삽입
dq가 비어 있지 않은 동안 수행
- dq_size :=dq의 크기
- temp :=새 목록
- 인덱스 :=-1
- 0에서 dq_size 범위의 각 값에 대해 수행
  - node :=dq에서 마지막 요소 삭제
  - 노드의 왼쪽이 비어 있지 않으면
    - 노드의 왼쪽을 dq의 끝에 추가
  - 노드의 오른쪽이 비어 있지 않으면
    - 노드의 오른쪽을 dq의 끝에 추가
  - temp의 끝에 노드 삽입
  - 노드가 u와 같으면
    - 인덱스 :=임시 크기 - 1
- 인덱스가 temp - 1의 크기와 같으면
  - null 반환
- 인덱스> -1이면
  - 반환 온도[인덱스 + 1]
null 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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 insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
            break
         else:
            que.append(temp.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 == None):
      return None
   if (root.val == element):
      return root
   res1 = search_node(root.left, element)
   if res1:
      return res1
   res2 = search_node(root.right, element)
   return res2
def solve(root, u):
   if not root:
      return None
   dq = deque()
   dq.append(root)
   while dq:
      dq_size = len(dq)
      temp = []
      index = -1
      for _ in range(dq_size):
         node = dq.pop()
         if node.left:
            dq.appendleft(node.left)
         if node.right:
            dq.appendleft(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)
ret = solve(root, u)
print(ret.val)

입력

root = make_tree([5, 3, 7, 2, 4, 6, 8])
u = search_node(root,6)