LeetCode 236 - Lowest Common Ancestor of a Binary Tree (Medium)

문제

LeetCode - 236번

풀이 과정

이진 트리가 주어질 때 가장 가까운 공통 조상을 찾는 문제입니다.
여기서 가장 가까운 조상 노드가 되기 위해서는 두 가지 경우의 형태를 가집니다.

    q (A)    a (A)
   /        / \
  b        b   q
 /        /
p        p

위 그림에서 p & q 의 공통 조상 중 가장 가까운 노드는 전자의 경우 q 이고 후자의 경우 a 가 됩니다.

이를 통해 우리가 찾는 조상 노드 A 는 왼쪽과 오른쪽 서브트리에 각각 p 혹은 q 가 존재하거나
조상 노드 A 를 포함하고 나머지 한 노드가 왼쪽 혹은 오른쪽 서브트리에 존재하는 형태를 가집니다.

따라서 DFS 를 수행하며 우리가 찾는 타켓 노드 p, q 의 존재 유무를 판단하고
현재 루트 노드를 포함해서 자식들 중 p 혹은 q 가 모두 발견되는 첫 루트 노드를 찾으면 됩니다.

코드

/**
 * 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) {
  let ancestor = null;

  function dfs(root, depth) {
    if (!root) return false;

    const here = root === p || root === q;
    const left = dfs(root.left, depth + 1);
    const right = dfs(root.right, depth + 1);

    if ([here, left, right].filter((x) => x).length === 2) {
      ancestor = root;
    }

    return here || left || right;
  }

  dfs(root, 0);

  return ancestor;
};