[LeetCode] 993. Cousins in Binary Tree

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

Cousins in Binary Tree - LeetCode

---

문제

각 노드가 유니크한 값을 갖는 이진트리의 $root$와 두 다른 노드의 값 $x$와 $y$가 주어진다. 두 노드 $x$, $y$가 사촌 관계라면 $true$를 반환하고, 그렇지 않다면 $false$를 반환하라.

 

두 노드가 부모 노드는 다르지만, 같은 깊이에 위치해 있다면 사촌 관계이다.

 

이진트리에서 루트 노드는 깊이가 $0$이고, 깊이 $k$의 자식 노드의 깊이는 $k+1$이다.

예제

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

---

풀이

트리 탐색 기법인 DFS 또는 BFS를 활용하여 문제를 풀 수 있습니다.

 

트리를 탐색하면서 $x$와 $y$노드를 찾고, 해당 노드의 부모와 자신의 깊이를 기록해둡니다. 이후, 두 노드가 사촌 관계인지를 파악하는 방식으로 문제의 해답을 구할 수 있습니다.

 

여기서는 DFS를 활용하여 트리를 탐색하도록 하겠습니다. 다음은 재귀를 활용한 기본적인 DFS 코드를 활용하여 $x$와 $y$ 노드를 찾는 코드입니다.

function dfs(root){
    if (!root) { return; }
    
    if (x === root.val) { ... }
    if (y === root.val) { ... }
    
    dfs(root.left);
    dfs(root.right);
}

$x$와 $y$가 사촌 관계임을 확인하기 위해서는 두 가지 정보(부모, 깊이)가 필요함을 알고 있습니다. 이를 위해서 다음과 같이 코드를 수정할 수 있습니다.

function dfs(root, parent, depth){
    if (!root) { return; }
    
    if (x === root.val) { ... }
    if (y === root.val) { ... }
    
    dfs(root.left, root.val, depth+1);
    dfs(root.right, root.val, depth+1);
}

매개변수로 부모 노드의 값과 현재 노드의 depth를 입력받는 것입니다. 이렇게 수정하면 $x$와 $y$ 노드를 찾았을 때 매개변수로 들어온 값을 저장하는 것으로 두 노드가 사촌관계임을 확인하는데 필요한 모든 정보를 알 수 있습니다.

 

최종적으로 비워두었던 코드를 채우면 다음과 같은 코드가 됩니다.

const xInfo = {};
const yInfo = {};

function dfs(root, parent, depth){
    if (!root) { return; }
    
    if (x === root.val) { xInfo.parent = parent; xInfo.depth = depth; }
    if (y === root.val) { yInfo.parent = parent; yInfo.depth = depth; }
    
    dfs(root.left, root.val, depth+1);
    dfs(root.right, root.val, depth+1);
}

자, 이제 정말 마지막으로 두 노드가 사촌 관계인지를 확인하여 반환하는 코드를 작성하는 것으로 문제에서 원하는 답을 구할 수 있습니다.

var isCousins = function(root, x, y) {
    const xInfo = {}
    const yInfo = {}
    
    function dfs(root, parent, depth) {
        if (!root) { return; }
        if (root.val === x) { xInfo.parent = parent; xInfo.depth = depth; }
        if (root.val === y) { yInfo.parent = parent; yInfo.depth = depth; }
        
        dfs(root.left, root.val, depth+1);
        dfs(root.right, root.val, depth+1);
        
        return;
    }
    
    dfs(root, -1, 0);
    
    if (xInfo.depth === yInfo.depth && xInfo.parent !== yInfo.parent) {
        return true;
    }
    
    return false;
};

알고리즘의 시간 복잡도에 대해서 생각해보면, DFS로 트리를 탐색하는데 걸리는 시간이 이 알고리즘의 시간 복잡도가 됩니다. 즉, $O(N)$이 될 것입니다. 이때 $N$은 트리의 노드 개수가 됩니다.

 

Github: 993.js

GitHub - opwe37/Algorithm-Study