Python에서 이진 트리의 잎 및 비 잎 노드를 찾는 프로그램

이진 트리가 있다고 가정하고 첫 번째 숫자는 트리의 잎 개수이고 두 번째 숫자는 잎이 아닌 노드의 개수인 두 개의 숫자 목록을 찾아야 합니다.

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

3개의 잎과 2개의 잎이 아닌 노드가 있으므로 출력은 (3, 2)가 됩니다.

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

• n이 null이면
  • 반환(0, 0)
• n의 왼쪽이 null이고 n의 오른쪽이 null이면
  • 반환(1, 0)
• left :=해결(n의 왼쪽)
• right :=해결(n의 오른쪽)
• 반환(왼쪽[0] + 오른쪽[0], 1 + 왼쪽[1] + 오른쪽[1])

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

예시

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, n):
      if not n:
         return 0, 0
      if not n.left and not n.right:
         return 1, 0
      left, right = self.solve(n.left), self.solve(n.right)
      return left[0] + right[0], 1 + left[1] + right[1]
ob = Solution()
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)
print(ob.solve(root))

입력

root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)

출력

(3, 2)