이진 트리가 하나 있다고 가정해 보겠습니다. 우리는 값이 짝수인 모든 잎(리프) 노드를 반복적으로 삭제하는 작업을 수행할 것입니다. 잎 노드를 모두 제거한 후 트리에 루트만 남아 있고 그 값마저 짝수라면, 루트 노드 역시 삭제됩니다.
예를 들어 입력 트리가 다음과 같다면,
출력 결과는 다음과 같습니다.
이 문제를 해결하기 위해 다음과 같은 단계를 따릅니다.
solve() 함수를 정의합니다. 이 함수는 루트 노드(root)를 매개변수로 받습니다.
root가 null이면 null을 그대로 반환합니다.
root의 왼쪽 자식 := solve(root의 왼쪽 자식)
root의 오른쪽 자식 := solve(root의 오른쪽 자식)
root가 잎 노드이면서 저장된 값이 짝수라면 null을 반환합니다.
그 외의 경우에는 root를 그대로 반환합니다.
여기서 핵심은 후위 순회(post-order) 방식이라는 점입니다. 자식 노드를 먼저 처리하기 때문에, 자식이 삭제되어 새롭게 잎 노드가 된 부모 노드까지 빠짐없이 검사하고 제거할 수 있습니다. 이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다.
예제
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def inorder(root):
if root:
inorder(root.left)
print(root.data, end = ', ')
inorder(root.right)
class Solution:
def solve(self, root):
if not root:
return None
root.left = self.solve(root.left)
root.right = self.solve(root.right)
if not root.left and not root.right and root.data % 2 == 0:
return None
return root
ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
ob.solve(root)
inorder(root)
입력
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
출력
13, 16, 7, 14,
실행 결과를 살펴보면 짝수 값을 가진 잎 노드인 12와 4, 22가 먼저 삭제되고, 그 결과 하나뿐인 자식을 가지게 된 노드들은 여전히 잎 노드가 아니므로 그대로 유지됩니다. 마지막으로 중위 순회(inorder)로 트리를 출력하면 13, 16, 7, 14 순서로 남아 있는 노드들을 확인할 수 있습니다.