Python으로 이진 트리의 모든 노드 값이 동일한지 확인하는 프로그램

이진 트리(binary tree)가 주어졌을 때, 트리 내 모든 노드의 값이 서로 동일한지 확인해야 하는 문제를 생각해 볼 수 있습니다.

예를 들어, 다음과 같은 입력이 주어진다면

모든 노드가 같은 값을 가지므로 출력 결과는 True가 됩니다.

문제 해결 접근 방식

이 문제는 재귀(Recursion)를 활용하면 간단하게 해결할 수 있습니다. 해결 과정은 다음과 같습니다.

• solve() 함수를 정의합니다. 이 함수는 루트 노드(root)와 비교 기준 값(val)을 매개변수로 받습니다.

• 루트 노드가 null인 경우에는 True를 반환합니다. 빈 트리는 모든 노드의 값이 동일하다고 간주할 수 있기 때문입니다.

• val 값이 아직 정의되지 않았다면, 현재 루트 노드의 값을 val로 설정합니다. 이는 최초 호출 시 기준값을 지정하는 역할을 합니다.

• 마지막으로, 루트 노드의 값이 val과 일치하고, 왼쪽 자식(left)과 오른쪽 자식(right)에 대해 solve() 함수를 재귀적으로 호출한 결과도 모두 참일 때만 True를 반환합니다.

예제 코드

아래 구현 예시를 통해 더 쉽게 이해할 수 있습니다.

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, val=None):
        if not root:
            return True
        if val is None:
            val = root.val
        return root.val == val and self.solve(root.left, val) and self.solve(root.right, val)

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(5)
root.right = TreeNode(5)
root.left.left = TreeNode(5)
root.left.right = TreeNode(5)
print(ob.solve(root))

입력

root = TreeNode(5)
root.left = TreeNode(5)
root.right = TreeNode(5)
root.left.left = TreeNode(5)
root.left.right = TreeNode(5)

출력

True

위 코드에서는 값이 5인 노드 5개로 구성된 이진 트리를 생성한 뒤 solve() 메서드를 호출했습니다. 모든 노드의 값이 5로 동일하기 때문에 결과로 True가 출력됩니다. 만약 하나라도 다른 값을 가진 노드가 있다면 False가 반환됩니다.

이 알고리즘은 트리의 모든 노드를 한 번씩 순회하므로 시간 복잡도는 O(n)이며, n은 트리의 전체 노드 개수입니다. 재귀 호출 깊이는 트리의 높이에 비례하므로, 깊이가 매우 깊은 트리의 경우 스택 오버플로우를 고려해야 할 수 있습니다.