Python의 루트에서 리프 경로에 노드가 충분하지 않음

이진 트리가 있다고 가정합니다. 이 노드를 교차하는 모든 루트에서 리프 경로로의 합이 제한보다 작으면 노드가 충분하지 않은 것으로 알려져 있습니다. 불충분한 모든 노드를 동시에 삭제하고 결과 바이너리 트리의 루트를 반환해야 합니다. 트리가 같음이고 한계가 1 −

그러면 출력 트리는 -

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

• solve() 메서드를 정의하면 뿌리를 내리고 제한됩니다.
• 노드에 왼쪽 및 오른쪽 하위 트리가 없으면
  • 루트 값이 1보다 작으면 null 반환, 그렇지 않으면 루트
• 루트가 하위 트리를 떠났다면 루트의 왼쪽 :=solve(루트의 왼쪽, 한계 – 루트의 값)
• 루트에 올바른 하위 트리가 있는 경우 루트의 오른쪽 :=solve(루트의 오른쪽, 한계 – 루트의 값)
• 루트에 왼쪽 하위 트리, 오른쪽 하위 트리 또는 둘 다 있으면 루트를 반환하고 그렇지 않으면 null을 반환합니다.

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

예

class Solution(object):
   def sufficientSubset(self, root, limit):
      """
      :type root: TreeNode
      :type limit: int
      :rtype: TreeNode
      """
      if not root.left and not root.right:
         return None if root.val<limit else root
      if root.left:
         root.left= self.sufficientSubset(root.left,limit-root.val)
      if root.right:
         root.right = self.sufficientSubset(root.right,limit-root.val)
      return root if root.left or root.right else None

입력

[1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14]
1

출력

[1,2,3,4,null,null,7,8,9,null,14]