Python에서 이진 트리 노드의 형제 값을 찾는 프로그램

값 k와 이진 탐색 트리가 있다고 가정합니다. 여기서 각 노드는 리프이거나 2개의 자식을 포함합니다. k 값을 포함하는 노드를 찾아 형제의 값을 반환해야 합니다.

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

k =4. 그러면 출력은 10이 됩니다.

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

• util() 함수를 정의합니다. 이것은 루트, k, 및

  를 취합니다.

• 루트의 왼쪽이 null이 아니고 루트의 오른쪽이 null이 아닌 경우

  • 반환

• k> 루트 값이면

  • 루트의 오른쪽 값이 k와 같으면

    • ans

      의 끝에 root의 왼쪽 값을 삽입합니다.

    • 반환

  • 그렇지 않으면

    • util(루트의 오른쪽, k, ans)

• k <루트 값이면

  • 루트의 오른쪽 값이 k와 같으면

    • ans

      끝에 root의 오른쪽 값 삽입

    • 반환

  • 그렇지 않으면

    • util(루트 왼쪽, k, ans)

• 기본 방법에서 다음을 수행하십시오 -

• ans :=새 목록

• util(루트, k, ans)

• 반환 [0]

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

예

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right

def util(root, k, ans):
   if root.left is None and root.right is None:
      return
   if k > root.val:
      if root.right.val == k:
         ans.append(root.left.val)
         return
      else:
         util(root.right, k, ans)
   if k < root.val:
      if root.left.val == k:
         ans.append(root.right.val)
         return
      else:
         util(root.left, k, ans)

class Solution:
   def solve(self, root, k):
      ans = []
      util(root, k, ans)
      return ans[0]

root = TreeNode(6)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
ob1 = Solution()
print(ob1.solve(root, 4))

입력

root = TreeNode(6)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
4

출력

10