[LeetCode] 236. Lowest Common Ancestor of a Binary Tree

문제 출처: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Lowest Common Ancestor of a Binary Tree - LeetCode

 

문제

이진트리에서 두 노드 간의 최소 공통 조상(Lowest Common Ancestor, LCA)을 찾아라.

 

위키디피디아의 LCA 정의에 따르면 다음과 같다: "LCA는 두 노드 p와 q 모두를 후손으로 갖는 가장 낮은(lowest) 노드 T로 정의된다(자기 자신 노드 또한 자신의 후손 노드로 고려한다)."

 

예제

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3

Explanation: The LCA of nodes 5 and 1 is 3.

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5

Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

 

풀이

트리 탐색 알고리즘 중 DFS 방식을 이용하여 접근하였다. DFS 방식을 사용할 경우, 이전에 탐색한 노드와 현재 탐색 중인 노드 간 계층 관계가 형성되어 탐색 결과를 하나로 취합하기 적합한 구조라 생각했기 때문이다.

 

DFS로 탐색을 수행하게 되면, 리프 노드를 제외한 각 노드는 3가지 정보를 갖고 있다고 생각할 수 있다.

1. 현재 노드 값과 p, q 사이의 비교 결과
2. 왼쪽 서브 트리가 p, q 중 어떤 노드를 갖고 있는지에 대한 정보
3. 오른쪽 서브 트리가 p, q 중 어떤 노드를 갖고 있는지에 대한 정보

 

이 정보들을 토대로 현재 노드를 루트로 하는 서브 트리가 p, q 중 어떤 노드를 갖고 있는지에 대한 하나의 결과를 도출할 수 있고 이를 부모 노드에 반환하는 형식으로 부모 노드가 3개의 정보를 온전히 갖게 되도록 하는 과정을 반복할 수 있다.

 

3개의 정보를 하나로 취합하는 방식에 대해 생각해보면, 만약, 현재 노드와 p, q 사이의 비교 결과가 [false, false]이고, 왼쪽 서브 트리와 오른쪽 서브 트리의 결과가 각각 [true, false], [false, true]라 하자. 그렇다면 현재 노드를 루트로 하는 서브 트리는 [true, true]가 된다. 즉, p와 q를 모두 갖고 있다는 뜻이다.

 

DFS로 탐색을 진행하기 때문에, 리프노드부터 단계적으로 각 노드가 루트인 서브 트리가 p, q 중 어떤 값들을 갖고 있는지 체크할 수 있고, 결국 최초로 p와 q를 동시에 갖는 노드가 찾고자 하는 노드가 된다.

 

이를 코드로 작성하면 다음과 같다.

var lowestCommonAncestor = function(root, p, q) {
    let ancestor = null;

    function dfs(root, p, q) {
        if (ancestor != null) { return [0, 0]; }

        const left = root.left != null ? dfs(root.left, p, q) : [false, false];
        const right = root.right != null ? dfs(root.right, p, q) : [false, false];

        const cur = [0, 0];
        cur[0] = (root.val == p.val) | left[0] | right[0];
        cur[1] = (root.val == q.val) | left[1] | right[1];

        if (ancestor == null && cur[0] && cur[1]) { ancestor = root; }

        return cur;
    }

    dfs(root, p ,q);

    return ancestor;
};

 

Github: 236.js

opwe37/Algorithm-Study