파이썬에서 이진 트리의 가장 긴 교대 경로의 길이를 찾는 프로그램

<시간/>

이진 트리가 있다고 가정하고 왼쪽과 오른쪽 자식을 번갈아 가며 아래로 내려가는 가장 긴 경로를 찾아야 합니다.

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

대체 경로가 [2, 4, 5, 7, 8]이므로 출력은 5가 됩니다.

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

루트가 null이면
- 0을 반환
dfs() 함수를 정의합니다. 노드, 개수, 플래그가 필요합니다.
노드가 null이 아니면
- 플래그가 True와 같으면
  - a :=dfs(노드 왼쪽, 개수 + 1, 거짓)
  - b :=dfs(노드 오른쪽, 1, True)
- 그렇지 않으면 플래그가 False와 같을 때
  - a :=dfs(노드 오른쪽, 개수 + 1, True)
  - b :=dfs(노드 왼쪽, 1, False)
- , b의 최대값을 반환
반환 횟수
기본 방법에서 다음을 수행합니다.
a :=dfs(루트 왼쪽, 1, False)
b :=dfs(루트의 오른쪽, 1, True)
, b의 최대값을 반환

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

예시

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

class Solution:
   def solve(self, root):
      if not root:
         return 0

      def dfs(node, count, flag):
         if node:
            if flag == True:
               a = dfs(node.left, count + 1, False)
               b = dfs(node.right, 1, True)
            elif flag == False:
               a = dfs(node.right, count + 1, True)
               b = dfs(node.left, 1, False)

            return max(a, b)
      return count

      a = dfs(root.left, 1, False)
      b = dfs(root.right, 1, True)

   return max(a, b)

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.right = TreeNode(7)
root.right.left.right.left = TreeNode(8)
print(ob.solve(root))

입력

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