파이썬에서 이진 트리의 유일한 자식 수를 찾는 프로그램

이진 트리가 있다고 가정합니다. 우리는 유일한 자식 노드의 수를 찾아야 합니다. 우리가 알고 있듯이 노드 x는 부모가 x라는 정확히 하나의 자식을 가질 때 유일한 자식 노드라고 합니다.

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

8과 6이 유일한 자식이므로 출력은 2가 됩니다.

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

• 루트가 null이면
  • 0을 반환
• d :=이중 종료 대기열
• d 끝에 루트 삽입
• 카운트:=0
• d가 비어 있지 않은 동안 do
  • current :=d의 왼쪽 요소 및 왼쪽 요소 삭제
  • 현재 왼쪽이 null이 아니면
    • d에 전류의 왼쪽 삽입
    • 현재의 오른쪽이 null이면
      • 카운트 :=카운트 + 1
    • 현재의 권리가 null이 아니면
      • d에 전류의 오른쪽 삽입
      • 현재의 왼쪽이 null이면
        • 카운트 :=카운트 + 1
• 반환 횟수

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시 코드

from collections import deque

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 not root:
         return 0
      d = deque()
      d.append(root)
      count = 0
      while d:
         current = d.popleft()
         if current.left:
            d.append(current.left)
            if not current.right:
               count += 1
            if current.right:
               d.append(current.right)
               if not current.left:
                  count += 1
         return count

ob = Solution()
root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.right = TreeNode(8)
root.right.right = TreeNode(6)
print(ob.solve(root))

입력

root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.right = TreeNode(8)
root.right.right = TreeNode(6)

출력

2