Python에서 이진 트리의 가장 긴 짝수 값 경로를 찾는 프로그램

이진 트리가 있다고 가정하면 트리의 두 노드 사이에서 짝수 값으로 구성된 가장 긴 경로를 찾아야 합니다.

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

가장 긴 경로가 [10, 2, 4, 8, 6]이므로 출력은 5가 됩니다.

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

• 답변 :=0

• find() 함수를 정의합니다. 노드가 필요합니다.

• 노드가 null이면

  • 리턴(-1, -1)

• leftCnt :=find(노드 왼쪽)의 반환값의 최대값 + 1

• rightCnt :=find(노드 오른쪽)의 반환값의 최대값 + 1

• 노드의 값이 짝수이면

  • ans :=ans의 최대값 및 (leftCnt + rightCnt + 1)

  • 리턴(leftCnt, rightCnt)

• 그렇지 않으면

  • ans :=ans, leftCnt 및 rightCnt의 최대값

  • 리턴(-1, -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):
      ans = 0
      def find(node):
         nonlocal ans
         if not node:
            return -1, -1
         leftCnt = max(find(node.left)) + 1
         rightCnt = max(find(node.right)) + 1
         if node.val % 2 == 0:
            ans = max(ans, leftCnt + rightCnt + 1)
            return leftCnt, rightCnt
         else:
            ans = max(ans, max(leftCnt, rightCnt))
            return -1, -1
      find(root)
      return ans
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)

출력

5