Python에서 합이 짝수인 가장 긴 경로의 길이를 찾는 프로그램

이진 트리가 있다고 가정합니다. 합이 짝수인 가장 긴 경로의 길이를 찾아야 합니다.

따라서 입력이 이미지와 같으면 경로가 [5, 2, 4, 8, 5], sum =24(짝수)이므로 출력은 5가 됩니다.

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

• dfs() 함수를 정의합니다. 노드가 필요합니다.
• 노드가 null이면
  • 쌍(0, -inf)을 반환
• (left_0, left_1) :=dfs(노드의 왼쪽)
• (right_0, right_1) :=dfs(노드의 오른쪽)
• 노드 값이 홀수이면
  • ans :=ans의 최대값, (left_1 + right_0 + 1) 및 (left_0 + right_1 + 1)
  • 쌍((left_1 + 1), (right_1 + 1) 및 0의 최대값, (left_0 + 1) 및 (right_0 + 1)의 최대값)을 반환
• 그렇지 않으면
  • ans :=ans의 최대값, (left_0 + right_0 + 1) 및 (left_1 + right_1 + 1)
  • 쌍을 반환합니다(최대 (left_0 + 1), (right_0 + 1), 0), 최대 (left_1 + 1), (right_1 + 1))
• 메인 방법에서 다음을 수행하십시오 -
• ans :=0
• 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(node):
         if not node:
            return 0, float("-inf")
         left_0, left_1 = dfs(node.left)
         right_0, right_1 = dfs(node.right)
         if node.val & 1:
            self.ans = max(self.ans, left_1 + right_0 + 1, left_0 + right_1 + 1)
            return max(left_1 + 1, right_1 + 1, 0), max(left_0 + 1, right_0 + 1)
         else:
            self.ans = max(self.ans, left_0 + right_0 + 1, left_1 + right_1 + 1)
            return max(left_0 + 1, right_0 + 1, 0), max(left_1 + 1, right_1 + 1)
   self.ans = 0
   dfs(root)
   return self.ans
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(5)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(5)
print(ob.solve(root))

입력

root = TreeNode(2)
root.left = TreeNode(5)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(5)

출력

5