Python을 사용하여 좋은 리프 노드 쌍의 수를 찾는 프로그램

이진 트리가 있다고 가정합니다. 및 또 다른 값 거리 d. 두 노드 사이의 최단 경로가 거리 d보다 작거나 같을 때 두 개의 서로 다른 잎 노드 쌍을 양호하다고 합니다.

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

그리고 거리 d =4이면 경로 길이 거리가 2이므로 쌍은 (8,7) 및 (5,6)이지만 (7,5) 또는 (8,6) 또는 다른 쌍이기 때문에 출력은 2가 됩니다. 경로 길이가 d =4보다 큰 5이므로 좋지 않습니다.

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

• 솔 :=0

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

• 루트가 null이면

  • 새 목록 반환

• 루트가 잎이면

  • 한 쌍의 배열을 반환 [0, 0]

• 그렇지 않으면

  • cur :=새 목록

  • l :=util(루트 왼쪽)

  • r :=util(루트 오른쪽)

  • l의 각 n에 대해 수행

    • n[1] :=n[1] + 1

  • r의 각 n에 대해

    • n[1] :=n[1] + 1

  • r의 각 n에 대해

    • l의 각 n1에 대해 수행

      • n[1] + n1[1] <=d이면

        • 솔 :=솔 + 1

  • l+r을 반환

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

• 유틸리티(루트)

• 리턴 솔

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

예시

class TreeNode:
def __init__(self, val=0, left=None, right=None):
   self.val = val
   self.left = left
   self.right = right
class Solution:
   def __init__(self):
      self.sol = 0
   def solve(self, root, d):
      def util(root):
         if not root:
            return []
         if not root.left and not root.right:
            return [[0, 0]]
         else:
            cur = []
            l = util(root.left)
            r = util(root.right)
            for n in l:
               n[1] += 1
            for n in r:
               n[1] += 1
            for n in r:
               for n1 in l:
                  if n[1] + n1[1] <= d:
                     self.sol += 1
            return l+r
      util(root)
      return self.sol
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
d = 4
ob = Solution()
print(ob.solve(root, d))

입력

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
d = 4

출력

2