[DFS]leetcode 1110. Delete Nodes And Return Forest

낭만개발자·2022년 3월 21일
0

알고리즘

목록 보기
9/20

문제

  1. Delete Nodes And Return Forest
    Medium

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Example 1:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]
Example 2:

Input: root = [1,2,4,null,3], to_delete = [3]
Output: [[1,2,4]]

Constraints:

The number of nodes in the given tree is at most 1000.
Each node has a distinct value between 1 and 1000.
to_delete.length <= 1000
to_delete contains distinct values between 1 and 1000.

문제 설명

주어진 이진 트리에서 주어진 to_delete 배열의 수와 일치한 트리 노드 값을 삭제하고, 트리노드 자료형 배열로 반환하라, 라는 문제이다.
다만, 만약 트리중 Parents Node 가 삭제되었다면, left나 right의 자식노드들은 하나의 추가적 요소로 답 배열에 담긴다.
즉, 부모가 삭제되면 자식은 조각, 파편된 채로 답안 배열에 담아라 라는 말이다

풀이

의사코드

  1. DeptsFristSearch 탐색을 사용한다. left -> right 탐색 순이며, 우선 to_Delete 배열 숫자와 상관없이 전체 node를 answer 배열에 push 해둔다.
  1. dfs 함수를 만드는데, 이 문제의 가장 중요한 포인트인데..~(이걸 몰라서 못품)~ dsf(Node) -> Node 이거나 Null인 점이다. 즉 dsf(node)에 어느 한 node가 들어갔다면, 함수의 return으로 원상태 node가 리턴 되거나, null이 되어 기존 노드에 할당되는 형태이다. 만약 to_Delete 와 같은 삭제할 숫자라면, return null이 되어 원래 주소값에 할당될 것이며, 삭제할 숫자가 아니라면 return node가 되어 원래 주소값에 할당된다.
    ex) node.left = dsf(node.left) => node.left가 to_Delete 숫자면 return 으로 null이, 아니면 node.left가 node.left에 그대로 할당된다.
  1. 문제 중해서 탐색 해야하는 인풋 수열들 즉, for 문 돌려야 하는 배열 같은 경우, 중복 값이 없다면 new set()을 사용해서 set.has(대상변수)로 사용한다.

코드

초기 트리 변수 셋팅

to_delete 값 set함수 사용, dsf 함수 설계

#18행 같이 탐색해야할 to_delete 배열 같은 경우는 set에 담고, #32행 처럼 set.has()로 사용한다. 여기서 전체 초기노드(root 변수)를 push하는데, 만약 삭제할 타겟이 아니라면 일단 answer 배열에 push 해두는 것이다.
answer 배열에 push 하더라도 주소값은 변하지 않아, dsf 함수에서 root(=함수내 node 지역변수)를 조작하더라도 다 반영이 되므로, 굳이 마지막에 answer 배열에 push 할 필요가 없다.

  • dsf 함수
    함수 내에 중요한 것은 return으로 node를 해주는 것인데, 위 사진처럼 설정하면, 어떻게 작동하냐면, #23행에 dsf(node.left)가 콜 되면서 Stack에는 node.left 파라미터로 콜한 dsf 함수가 쌓인다(보기 편하게 그냥 파라미터값 node.left로 적었다.)그리고 = 왼쪽 node.left 함수로 할당되면서 Stack에 가장 상위에 있는 node.left는 제거되고, 아까 말한 return node 로 인해 해당 node가 그대로 node.left 주소에 할당되는 것이다. 즉 원복, 원래값에 그대로 할당되는 원리이다.

이제 원래거에 원래거를 그대로 할당하니까, 만약 set.has()조건, 즉 삭제 조건에 맞으면 1. answer에 push 해주고 2. null을 리턴해주는 로직을 추가 해주면 된다.
아래 추가해보자

#24행 조건에 따라 22행 dsf(node.left)의 리턴값이 null 이 될수도, node(원래 값)이 될수도 있게 설계 되었다. 즉 to_delete 값과 일치하면 #25행 로직을 타서 node.left가 있으면 answer.push 해주고 right도 마찬가지로..
그 후 return null 하면, 부모 노드에선 해당 자식 노드는 null 값이 할당되어서 사라진 셈이고, 그 null로 변한 자식의 자식 노드(가 있다면)는 push가 되어 문제에서 요구한 대로 동작하게 된다.

포인트

DFS에서 햇갈리는게 return 을 어떻게 사용할 지? 이다. dfs(left), 또는 dfs(right)의 리턴 값은 부모노드에서 사용할 수 있다는 점을 명심하자. 전에 트리의 지름 구하는 부분에선 아마 더해서 사용했던것 같고 이 문제에선 node.left = dfs(node.left) 처럼 바로 자기 자신에게 할당해서 변경사항을 적용할 수 있도록 하였다.

profile
낭만닥터와 슬의를 보고 저런 개발자가 되어야 겠다고 꿈꿔봅니다.

0개의 댓글