May LeetCoding Challenge[Day7] - Cousins in Binary Tree

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.
Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Input: root = [1,2,3,4],
x = 4,
y = 3

Output: false

Input: root = [1,2,3,null,4,null,5],
x = 5,
y = 4
Output: true

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 해당 문제를 이해 못 하고, 알고리즘을 계속 접근했다.

 - 1시간 넘게 삽질을 하다가 인터넷 검색을 하게 됐고, 문제의 정의를 알아냈다.

 - 트리와 함께 x와 y가 주어진다. 이 때, 주어진 트리에 x와 y는 같은 depth에 있어야 한다. 동시에 x와 y의 부모는 달라야한다. 그게 성립하는가에 대한 문제였다.

 - 문제를 풀기 위해서 재귀함수를 생각했다.

 - explore()라는 함수는 2가지 일을 한다. 첫 번째로는, x와 y가 어떤 depth에 있는 지 찾아내는 역할을 한다.

 - x와 y를 찾을 때, Set에 parent를 저장하는 역할을 한다.

 - countLeft, countRight에는 x와 y에 대한 각각의 depth가 담겨져 있다.

 - Set은 중복된 값을 제거하기 때문에, size가 2여야 조건이 성립한다.

 - 서로 depth가 갖고, Set의 사이즈가 2라면, true, 그렇지 않으면 false.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 문제를 이해하는게 가장 어려웠다.

 

3. 내가 작성한 알고리즘

 

/**
 * 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) {
        Set<Integer> memory = new HashSet();
        
        int countLeft = explore(root, root.val, memory, 1, x);
        int countRight = explore(root, root.val, memory, 1, y);
        if(countLeft == countRight && memory.size() == 2){
            return true;
        }
        return false;
    }
    
    //depth가 같고, 부모가 달라야한다.
    private int explore(TreeNode node, int parent, Set<Integer> memory, int count, int target){
        if(node == null){
            return -1;
        }
        
        if(node.val == target){
            memory.add(parent);
            return count;
        }
        
        int countLeft = explore(node.left, node.val, memory, count+1, target);
        int countRight = explore(node.right, node.val, memory, count+1, target);
        
        return Math.max(countLeft, countRight);
    }
}

4. 내가 작성한 알고리즘 결과

 

 

5. 반성할 점

 - 문제를 이해하는게 알고리즘의 최우선이다.

 - 앞으로는 문제를 확실히 이해하고, 알고리즘을 풀자.

 

문제 : https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3322/

Account Login - LeetCode