993. Cousins in Binary Tree

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

문의는 댓글 바람.

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

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

문제 출처

Cousins in Binary Tree - LeetCode

[문제 설명]

이진트리에서 각각의 트리의 값은 유니크하다.

매개변수로 오는 x,y의 값을 가진 노드가 서로 cousine이면 true를 리턴, 다르면 false를 리턴.

cousine의 조건

1. 부모가 다르다.

2. 같은 계층이다.

 

[처음 생각한 접근 방법]

그냥 평범한 BFS 문제 느낌이다. 오랜만에 풀어서 그런지 헷갈렸다.

단순한 넓이우선보다는 한 계층을 한 사이클로 두고 풀어야 하는 느낌이 들었다.

가장 중요한 점은 한 계층을 검색했는데 x 또는 y 중에 하나만 나왔을 경우다.

예를 들어 depth 3에서 x를 찾았다. 그런데 y를 찾지 못했다.

이런 경우에는 만족하는 조건이 없는 걸로 보고, 모든 반복문을 중단한 후에 false를 리턴해줘야 한다.

->왜냐? y가 같은 계층에 없으면 cousine이 되는 조건 2번째에 어긋나기 때문이다.

class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        // 만약 이 계층에 x또는 y가 존재하면 true가 됨.
        boolean isExist = false;
        // 두 수의 합 x+y
        int sum = x + y;
        // 자식이 x또는 y인 부모를 담을 set
        Set<TreeNode> set = new HashSet<>();
        // BFS 구현을 위한 Queue
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // BFS
        while (!queue.isEmpty()) {
            // 현재 계층의 사이즈
            int size = queue.size();

            // 현재 계층의 요소만큼 반복
            while (size-- > 0) {
                TreeNode temp = queue.poll();

                if (temp.left != null) {
                    queue.offer(temp.left);
                    if (temp.left.val == x || temp.left.val == y) {
                        set.add(temp);
                        isExist = true;
                        sum -= temp.left.val;
                    }
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                    if (temp.right.val == x || temp.right.val == y) {
                        set.add(temp);
                        isExist = true;
                        sum -= temp.right.val;
                    }
                }
            }

            // x또는 y는 존재하나는데 둘다 못찾은 경우
            if (isExist == true && sum != 0) return false;
            // x와 y를 찾았고 부모가 두명인 경우
            else if (isExist == true && sum == 0 && set.size() == 2) return true;
        }

        return false;
    }
}

class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        boolean isExist = false;
        int sum = x + y;
        Set<TreeNode> set = new HashSet<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode temp = queue.poll();

                if (temp.left != null) {
                    queue.offer(temp.left);
                    if (temp.left.val == x || temp.left.val == y) {
                        set.add(temp);
                        isExist = true;
                        sum -= temp.left.val;
                    }
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                    if (temp.right.val == x || temp.right.val == y) {
                        set.add(temp);
                        isExist = true;
                        sum -= temp.right.val;
                    }
                }
            }
            if (isExist == true && sum != 0) return false;
            else if (isExist == true && sum == 0 && set.size() == 2) return true;
        }

        return false;
    }
}