파이썬에서 잎사귀를 제외한 각 노드 값이 자식 값의 합인지 확인하는 프로그램

이진 트리가 있다고 가정하고 나뭇잎을 제외한 트리의 모든 노드에 대해 해당 값이 왼쪽 자식 값과 오른쪽 자식 값의 합과 같은지 확인해야 합니다.

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

그러면 출력은 True

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

• dfs() 함수를 정의합니다. 이것은 뿌리를 내릴 것입니다

• 루트가 null이면

  • 참을 반환

• 루트의 왼쪽이 null이고 루트의 오른쪽이 null이면

  • 참을 반환

• 왼쪽 :=0

• 루트 왼쪽이 null이 아니면

  • left :=루트 왼쪽의 값

• 오른쪽 :=0

• 루트의 오른쪽이 null이 아니면

  • right :=루트의 오른쪽 값

• (왼쪽 + 오른쪽이 루트 값과 동일) dfs(루트 왼쪽)가 true이고 dfs(루트 오른쪽)가 true인 경우 true를 반환합니다.

• 주요 방법에서 다음을 수행하십시오 -

• 반환 dfs(루트)

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

예

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      def dfs(root):
         if root == None:
            return True
         if root.left == None and root.right == None:
            return True
         left = 0
         if root.left:
            left = root.left.val
         right = 0
         if root.right:
            right = root.right.val
         return (left + right == root.val) and dfs(root.left) and
      dfs(root.right)
return dfs(root)
ob = Solution()
root = TreeNode(18)
root.left = TreeNode(8)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
print(ob.solve(root))

입력

root = TreeNode(18) root.left = TreeNode(8) root.right = TreeNode(10)
root.left.left = TreeNode(3) root.left.right = TreeNode(5)

출력

True