[LeetCode/JAVA] 993. Cousins in Binary Tree

 

 

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다. 😊
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/cousins-in-binary-tree/

Cousins in Binary Tree - LeetCode

문제 설명

출처 : LeetCode

x, y로 주어진 값의 노드가 사촌인지 아닌지 반환하세요.

[사촌 여부 판단 기준]
1. 부모 node가 다르다.
2. depth가 같다.

 

풀이 방법

Set 인터페이스의 특징을 이용하여 구현하였습니다. (중복을 허용하지 않음)

1. target node를 찾아 해당 부모 node 및 depth를  각각의 Set에 넣어줍니다.
2. 부모를 담는 Set은 부모가 달라야 하므로 길이가 2 입니다.
3. 깊이를 담는 Set은 깊이가 같아야 하므로 길이가 1 입니다.

위 조건을 만족하지 않으면 false 반환, 이외는 true입니다.

내 코드(JAVA)

 

public class Solution {

    // Set의 특징을 이용한 풀이(중복을 허용하지 않음)
    public boolean isCousins(TreeNode root, int x, int y) {
        Queue<TreeNode> q = new LinkedList<>();
        Set<TreeNode> setParent = new HashSet<>();
        Set<Integer> setDepth = new HashSet<>();
        int depth = 0;

        q.add(root);

        while(!q.isEmpty()) {
            int size = q.size();

            for(int i=0; i<size; i++) {
                TreeNode node = q.poll();

                if(node.left != null) {
                    if(node.left.val == x || node.left.val == y) {
                        setParent.add(node);
                        setDepth.add(depth);
                    }
                    q.add(node.left);
                }

                if(node.right != null) {
                    if(node.right.val == x || node.right.val == y) {
                        setParent.add(node);
                        setDepth.add(depth);
                    }
                    q.add(node.right);
                }
            }
            depth++;
        }

        // 부모가 달라야한다, 깊이는 같아야한다
        if(setParent.size() < 2 || setDepth.size() > 1) return false;

        return true;
    }

}

 

오래간만에 BFS를 접하니 당황스러웠다.

꾸준히 해봅시다.