📌 문제 설명

Lowest Common Ancestor of a Binary Tree 문제 보기

📌 문제 접근

처음에는 주석을 읽지 않아서 인덱스로 풀려고 했다. 알고 보니까 leetcode는 이따금 이렇게 객체로 주는 문제도 있다고 한다. 탐색하기 좋은 객체를 주었으니 그에 맞춰 풀면 된다. 자기 자신과 양 옆의 자식 노드를 가지고 있으므로, 재귀적으로 탐색하면 된다.

현재 노드가 그에 맞다면 return을 하고 아니면 null을 반환하여 부모 노드에게 전달하면 되는 간단한 문제.

📌 내가 작성한 코드

/**
 * 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}
 */
const lowestCommonAncestor = (root, p, q) => {
  const dfs = (root) => {
    if (!root || root === p || root === q) return root;
    const left = dfs(root.left);
    const right = dfs(root.right);
    if (left && right) return root;
    return left || right;
  };
  return dfs(root);
};

📌 시간 복잡도

O(N) - 모든 노드를 한 번씩 방문하므로 (N: 트리 노드 수)

📌 참고 링크

• Lowest Common Ancestor - 위키백과