[2024] day 139. Leetcode 1325. Delete Leaves With a Given Value

gunny·2024년 5월 16일

leetcode 1325. Delete Leaves With a Given Value leetcode 1325. Delete Leaves With a Given Value python

코딩테스트

목록 보기

453/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 17일 (금)
Leetcode daily problem

1325. Delete Leaves With a Given Value

https://leetcode.com/problems/delete-leaves-with-a-given-value/

Problem

이진 트리 루트와 목표값 정수가 주어지면 목표 값을 가진 모든 리프 노드를 삭제한다.

값이 target인 리프 노드를 삭제한 후 해당 상위 노드가 리프 노드가 되고 값이 target인 경우 삭제되어야 한다는 점을 유의해야 한다(할 수 없을 때까지 계속해서 삭제해야 함)

Solution

dfs

dfs를 이용한 재귀 호출로 이진 트리에서 주어진 값을 가진 모든 리프 노드를 삭제한다.
후위 순회를 해가면서 자식 노드부터 처리한 후 부모 노드를 처리하는 후위 순회를 사용하면, 리프 노드를 제거한 후 부모 노드를 갱신할 수 있다.

root가 None이면 None을 반환하고, 서브 트리로 root의 왼쪽과 오른쪽 자식을 대상으로 재귀적으로 removeLeafNodes 함수를 호출한다.
그리고 현재 노드가 리프 노드인지 확인하고, 리프 노드이며 값이 target인 경우 None을 반환하고, 리프 노드가 아닌 경우 현재 노드를 그대로 반환하는 식으로 이진 트리를 업데이트 한다.

Code

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        if not root:
            return None
        
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)
        
        if not root.left and not root.right and root.val==target:
            return None
        
        return root