1325. Delete Leaves With a Given Value

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문제 출처

Delete Leaves With a Given Value - LeetCode

[문제 설명]

target과 같은 노드를 찾아서 부모를 제외한 인접 노드가 없으면 노드에서 지워버린다.

[처음 생각한 접근 방법]

노드 중에 자식이 target인 애를 stack에 넣고, 순서대로 빼서 제거해주기.

주어진 노드들을 BFS로 돕니다. target은 2입니다.

root 노드에 자식을 체크합니다. 값이 target인 자식이 있습니다.

자식에 target이 있으므로 스택에 넣습니다.

2를 검색합니다. 자식에 2가 있습니다.

자식에 target이 있으므로 스택에 넣습니다.

3을 검색합니다. 3에 자식으로 2랑 4가 있습니다.

자식에 target이 있으므로 3을 스택에 넣습니다.

2를 검색합니다. 자식이 없으므로 체크 안함.

2를 검색합니다. 자식이 없으므로 생략.

4를 검색합니다 자식이 없으므로 생략.

이제 스택에 쌓인 요소대로 차례대로 검색합니다.(FILO으로 인해 자동으로 밑에 있는 요소들부터 나옵니다.)

3을 확인합니다. 왼쪽이 2이므로 왼쪽을 null을 가리키게 합니다.

2를 확인합니다. 왼쪽이 2이므로 왼쪽을 null을 가리키게 합니다.

1을 검색합니다. 왼쪽이 2이므로 왼쪽을 null을 가르키게 합니다.

import java.util.Queue;
import java.util.Stack;

class Solution {
    public TreeNode removeLeafNodes(TreeNode root, int target) {
        //주어진 노드는 1이상 3000개 이하이므로 null처리 걱정x
        //bfs로 검색
        Queue<TreeNode> q = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        q.offer(root);

        while (!q.isEmpty()) {
            TreeNode temp = q.poll();

            //현재 노드에 left나 right중에 target과 같은 값이면 현재 노드를
            //스택에 넣음.(target에 부모를 넣는 거)
            if (temp.left != null) {
                q.offer(temp.left);
                if (temp.left.val == target) stack.push(temp);
            }
            if (temp.right != null) {
                q.offer(temp.right);
                if (temp.right.val == target) stack.push(temp);
            }
        }

        //bfs가 끝나면 pop을 한번함.
        while (!stack.isEmpty()) {
            //target 값과 같은 노드에 부모가 나옴.
            TreeNode temp = stack.pop();
            //left right체크하고, target과 같은 애가 둘 중에 무조건 하나는 있음.
            //그러면 걔에 left right를 체크하고 둘다 null이면 부모에서 left와 right중 하나를 없앰.(target인 노드가 있는 곳.)
            if (temp.left != null && temp.left.val == target) {
                if (temp.left.left == null && temp.left.right == null) {
                    temp.left = null;
                }
            }
            if (temp.right != null && temp.right.val == target) {
                if (temp.right.left == null && temp.right.right == null) {
                    temp.right = null;
                }
            }
        }

        if (root.left == null && root.right == null && root.val == target) {
            root = null;
        }

        return root;
    }
}

풀긴 풀었는데 속도는 2~3ms로 좀 느리다.

 

[리트코드 답안]

public TreeNode removeLeafNodes(TreeNode root, int target) {
    if (root.left != null) root.left = removeLeafNodes(root.left, target);
    if (root.right != null) root.right = removeLeafNodes(root.right, target);
    
    return root.left == root.right && root.val == target ? null : root;
}

난 당연히 카테고리를 BFS로 고르고 푼 문제라서 당연히 BFS 답안이 여러개 있을 줄 알았는데, 재귀로 푼 답안이 대다수였다.

어렵다고 피하지만 말고 슬슬 재귀 문제 연습을 해야할 거 같다. 시간복잡도랑 공간복잡도도.