Python에서 이진 트리의 루트에서 잎까지 가장 긴 합 경로의 합을 찾는 프로그램

<시간/>

이진 트리가 있다고 가정하고 루트에서 리프 노드까지의 가장 긴 경로의 합을 찾아야 합니다. 동일한 긴 경로가 두 개 있으면 합이 더 큰 경로를 반환합니다.

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

그러면 출력은 20이 됩니다.

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

함수 rec() 를 정의하십시오. 시간이 걸립니다
curr이 null이면
- 리턴(0, 0)
더 큰 :=최대 rec(curr의 왼쪽) , rec(curr의 오른쪽)
쌍을 반환(더 큰[0] + 1, 더 큰[1] + curr의 값)
주요 방법에서 다음을 수행하십시오 -
ret :=rec(루트)
ret의 1번째 인덱스를 반환

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

예

class TreeNode:
   def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

class Solution:
   def solve(self, root):
      def rec(curr):
         if not curr:
            return (0, 0)
         bigger = max(rec(curr.left), rec(curr.right))
         return (bigger[0] + 1, bigger[1] + curr.val)
      return rec(root)[1]
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

입력

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