파이썬에서 이진 트리 경로의 가장 큰 합을 찾는 프로그램

이진 트리가 있다고 가정하고 루트 노드에서 리프 노드로 가는 경로의 가장 큰 합을 찾아야 합니다.

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

루트에서와 같이 출력은 29가 되고 5-<9-<7-<8 경로를 따르면 추가 후 29가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따르겠습니다-

• Walk() 함수를 정의하십시오. 노드가 필요합니다. s

• 노드가 null이면

  • max_sum :=max_sum 및 s의 최대값

  • 반환

• s :=s + 노드의 데이터

• 걷기(노드 왼쪽, s)

• 걷기(노드 오른쪽, s)

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

• max_sum :=0

• 도보(루트, 0)

• max_sum 반환

더 나은 이해를 위해 다음 구현을 살펴보겠습니다-

예

from collections import defaultdict
   class TreeNode:
      def __init__(self, data, left = None, right = None):
         self.data = data
         self.left = left
         self.right = right
   class Solution:
      def walk(self, node, s):
         if not node:
            self.max_sum = max(self.max_sum, s)
         return
      s += node.data
      self.walk(node.left, s)
      self.walk(node.right, s)
   def solve(self, root):
      self.max_sum = 0
      self.walk(root, 0)
   return self.max_sum
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

입력

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)

출력

29