이진 트리(binary tree)가 하나 주어졌다고 가정해 봅시다. 이때 잎(리프) 노드를 제외한 모든 노드에 대해, 해당 노드의 값이 왼쪽 자식의 값과 오른쪽 자식의 값을 더한 것과 같은지 확인해야 합니다.
예를 들어 입력 트리가 다음과 같다면,
출력 결과는 True가 됩니다. 루트 노드 18은 왼쪽 자식 8과 오른쪽 자식 10의 합(8 + 10 = 18)과 같고, 노드 8 역시 자식인 3과 5의 합(3 + 5 = 8)과 일치하기 때문입니다.
문제 해결 접근 방법
이 문제는 깊이 우선 탐색(DFS)을 재귀적으로 활용하면 간단하게 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- 루트 노드를 인자로 받는
dfs()함수를 정의합니다. - 루트가
null(None)이라면True를 반환합니다. 빈 트리는 조건을 만족하는 것으로 간주합니다. - 왼쪽 자식과 오른쪽 자식이 모두 없는 경우, 즉 현재 노드가 잎 노드라면 검사 대상에서 제외되므로
True를 반환합니다. left변수를 0으로 초기화하고, 왼쪽 자식이 존재하면 그 값을 저장합니다.right변수를 0으로 초기화하고, 오른쪽 자식이 존재하면 그 값을 저장합니다.- (left + right == 현재 노드의 값)이 성립하고, 왼쪽 서브트리와 오른쪽 서브트리에 대한
dfs()호출 결과도 모두 참일 때True를 반환합니다. - 메인 메서드에서는 루트 노드에 대해
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(root):
if root == None:
return True
if root.left == None and root.right == None:
return True
left = 0
if root.left:
left = root.left.val
right = 0
if root.right:
right = root.right.val
return (left + right == root.val) and dfs(root.left) and dfs(root.right)
return dfs(root)
ob = Solution()
root = TreeNode(18)
root.left = TreeNode(8)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
print(ob.solve(root))
입력
root = TreeNode(18)
root.left = TreeNode(8)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
출력
True
복잡도 분석
이 알고리즘은 트리의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다. 여기서 n은 트리의 노드 개수입니다. 재귀 호출 스택의 깊이는 트리의 높이에 비례하므로, 공간 복잡도는 균형 잡힌 트리의 경우 O(log n), 편향된 트리의 경우 최악 O(n)입니다.