이진 트리의 루트가 있고 트리의 각 노드에 고유한 값이 있다고 가정합니다. to_delete에 값이 있는 모든 노드를 제거하면 포리스트가 남습니다. 우리는 남은 숲에서 나무의 뿌리를 찾아야 합니다. 따라서 입력이 다음과 같은 경우
to_delete 배열이 [3,5]와 같으면 출력은
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 배열 해상도 정의
- solve() 메서드를 정의하면 노드, to_delete 배열 및 노드가 루트인지 여부를 알려주는 부울 유형 정보가 필요합니다. 이 메서드는 아래와 같이 작동합니다-
- 노드가 null이면 null을 반환합니다.
- flag :=노드의 값이 to_delete 배열에 있으면 true
- 플래그가 거짓이고 is_root가 참이면 노드를 res에 삽입
- 노드 왼쪽 :=해결(노드 왼쪽, to_delete, 플래그)
- 노드 오른쪽 :=solve(노드 오른쪽, to_delete, 플래그)
- 플래그가 설정되면 아무 것도 반환하지 않고, 그렇지 않으면 false를 반환합니다.
- solve(node, to_delete, true)와 같은 메인 메소드에서 solve() 메소드 호출
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution(object):def delNodes(self, root, to_delete):""" :type root:TreeNode :type to_delete:List[int] :rtype:List[TreeNode] """ to_delete =set(to_delete ) self.res =[] self.solve(root,to_delete,True) return self.res def solve(self,node,to_delete,is_root):노드가 아닌 경우:반환 없음 플래그 =node.val in to_delete if not 플래그 및 is_root:self.res.append(node) node.left =self.solve(node.left,to_delete,flag) node.right =self.solve(node.right,to_delete,flag) 플래그 else 노드인 경우 None을 반환입력
[1,2,3,4,5,6,7][3,5]출력
[[1,2,null,4],[6],[7]]