[Leetcode] 236. Lowest Common Ancestor of a Binary Tree - JS

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
이진 트리와 두 노드가 주어질 때, 두 노드의 최하위 공통 조상 노드를 반환하라.
최하위 공통 조상 노드는 두 노드를 모두 자손으로 갖는 가장 낮은 노드로 정의된다.
전달받은 두 노드 자체가 자손이 될수도 있다.

제한조건
--------------------
- 노드의 갯수는 2 ~ 10^5개이다.
- node.val은 유일한 값이다.
- p !== q

 

2. 접근 방법

접근방법
--------------------
자식 노드를 찾았을 때, 부모 노드를 기억하고 있어야 반환할 수 있다.

1. 루트에서 시작하여 p, q 인지 노드 확인
2. 둘다 아니면, left, right 서브트리로 구분하여 재귀호출
    - p, q를 찾으면 해당 node 반환
3. left, right 모두 존재하면 현재 노드가 곧 LCA이다.
4. left, right 하나만 존재하면, left 또는 right 중 null이 아닌 노드가 곧 LCA이다.

 

 

3. 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    function helper(node) {
        if (!node) return null;

        if (node === p || node === q) return node;

        const left = helper(node.left);
        const right = helper(node.right);

        if (left && right) return node;

        return left || right;
    }
    return helper(root)
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n) 

- 공간복잡도: O(1)

 

LCA를 구하는 방법을 떠올려봤다.

내가 생각한 방법은 p, q 노드를 찾아내고 찾은 노드의 자식 노드 중에 q, p가 존재하지 않으면 처음에 찾은 p, q가 LCA가 된다는 것이다.

하지만 이 방법은 프로그래밍적으로 접근하기 어려운 방법이었다.

 

그래서 GPT에게 물어보면서 공부했다.

 

LCA에 초점을 맞춰 root에서 부터 시작하니 현재 노드가 p, q이면 현재 노드(root)를 반환한다.

만약, 현재 노드가 p, q가 아니면 왼쪽 서브트리와 오른쪽 서브트리로 나눠서 left, right 값을 계산한다.

왼쪽 서브 트리와 오른쪽 서브 트리에 각각 p, q가 존재하면 이 때의 node를 반환하면 된다.

왜냐하면 node의 left, right 서브트리의 LCA가 node이므로...

 

만약, 왼쪽 서브 트리나 오른쪽 서브 트리 중 하나의 값이 null 이라면...

즉, 한쪽 서브 트리에 p, q가 편향되었을 경우에는 left, right 서브 트리 중 null이 아닌 node 값을 반환한다.

 

이진 트리의 문제를 여러 개 풀어보니 왼쪽 서브 트리, 오른쪽 서브 트리를 나눠서 재귀호출하여 조건에 맞는 node 값을 반환하여

left, right 서브 트리 값으로 저장하여 이를 가지고 조건을 확인하여 결과값을 도출하는 방식이 많이 보이는 것 같다.

 

해당 유형의 문제를 자주 복습하여 낯익게 해야겠다.