문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

고유한 값을 가진 이진 트리 root와 서로 다른 두 노드 x와 y의 값이 주어졌을 때, x와 y에 해당하는 노드들이 서로 친척 관계이면 true, 그렇지 않다면 false를 반환해라.

이진트리의 두 노드는 서로 다른 부모 노드를 가지면서 깊이가 같으면 친척관계이다.

Example

#1

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

#2

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

#3

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

Constraints

• 트리에 있는 노드의 수는 [2, 100] 범위에 있다.
• 1 <= Node.val <= 100
• 각 노드는 고유한 값을 가진다.
• x != y
• x와 y는 트리에 존재한다.

Solved

/**
 * 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) {
        TreeNode xNode = findNode(root, x);
        TreeNode yNode = findNode(root, y);

        return (findLevel(root, xNode, 0) == findLevel(root, yNode, 0)) &&
            !isSibling(root, xNode, yNode);
    }

    private TreeNode findNode(TreeNode node, int val){
        if(node == null){
            return null;
        }

        if(node.val == val){
            return node;
        }

        TreeNode n = findNode(node.left, val);

        if(n != null){
            return n;
        }

        return findNode(node.right, val);
    }

    private int findLevel(TreeNode root, TreeNode node, int level){
        if(root == null){
            return 0;
        }

        if(root == node){
            return level;
        }

        int l = findLevel(root.left, node, level + 1);

        if(l != 0){
            return l;
        }

        return findLevel(root.right, node, level + 1);
    }

    private boolean isSibling(TreeNode node, TreeNode x, TreeNode y){
        if(node == null){
            return false;
        }

        return(
            (node.left == x && node.right == y) ||
            (node.left == y && node.right == x) ||
            isSibling(node.left, x, y)||
            isSibling(node.right, x, y)
        );
    }
}