[리트코드] 993. Cousins in Binary Tree

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://leetcode.com/problems/cousins-in-binary-tree/

Cousins in Binary Tree - LeetCode

---

Think🤔

주어진 x,y의 노드 위치가 같으면 true를 반환하는 문제이다.

1. q를 먼저 만든다.

2. root를 q에 담아준다.

3. q가 빌떄까지 돌아준다.

4. 노드의 층(?)이랑 left right가 같은지 판별 

 

4번까지 적는데 세 번째의 경우는 위치가 같은데도 false가 나왔다. 2에 자식이 있어서 일까?

문제를 다시 살펴본 결과 부모가 달라야 한다.

부모도 비교를 해줘야 함.

 

5. 부모가 같은지를 어떻게 판별할까?

6. boolean 체크를 이용해서 처음에 판별을 먼저 한다. left right가 같으면 바로 false를 반환.

 이렇게 하면 같은 부모를 가질 수 없게 되고, 다음을 판별하면 된다.

7. 변수를 더 만들까 하다가 주어진 파라미터 x,y를 이용하기로 했다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        
        Queue<TreeNode> q = new LinkedList();
        
        q.offer(root);
        
        int count = 0; // 처음 0층
        
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                
                TreeNode node = q.poll();
                if(node.val == x){
                    x = count;            
                }
                if(node.val == y){
                    y = count;
                }
                
                if(node.left != null){
                    q.offer(node.left);
                }else if(node.right != null){
                    q.offer(node.right);
                }
            }
            count++;
            if(x == y){
                return true;
            }
        }
        
        return false;
    }
}

1,2,3, n,4, n,5를 넣으면 true가 나와야 하는데 false가 나온다 왜 false가 나오는 걸까..

결국 x랑 y가 같지 않은데 count로 같은 층은 ++하게 해 줬는데 도대체 why???

 

node.left!= null 이면 q.offer(node.left);를 하는 건 맞지만 else if!

right도 넣어줘야 하는데 if 한 번만 타고 if문이 끝나기 때문 그래서 else if로 적는 것이 아닌 if로 적어줘야 한다!

 

int형인 변수 xc, yc를 0으로 두고 풀 수 있지만 변수를 생성하지 않고 파라미터 값에 바로 값을 주는 방향으로 택했다

이제 부모가 같을 때를 처리해야 되는데 x, y값이 바뀌었을 때 if문을 만들어 줘야 한다.

 

근데 답이 맞지 않는다... 뭘까?

 

오타였다.. node.left.val node.left.val을 두 번 적어줬기 때문!

---

Solution✍

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        
        Queue<TreeNode> q = new LinkedList();
        
        q.offer(root);
        
        int count = 0; // 처음 0층
        
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                TreeNode node = q.poll();
                
                if(node.val == x){
                    x = count;            
                }
                if(node.val == y){
                    y = count;
                }
                
                if(node.left != null && node.right != null){
                    if(node.left.val == x && node.right.val == y){
                        return false;
                    }else if(node.left.val == y && node.right.val == x){
                        return false;
                    }
                }
                
                if(node.left != null){
                    q.offer(node.left);
                }
                if(node.right != null){
                    q.offer(node.right);
                }
            }
            count++;
            
            
            if(x == y && count > 0){
                return true;
            }
        }
        
        return false;
    }
}

---

 

Review🤩

if문에서 실수하지 말자...

---