[알고리즘] LeetCode 236. Lowest Common Ancestor of a Binary Tree JS

개요

이진트리가 주어지는데 여기서 가장 가까운 공통의 조상노드를 찾는 게 목적이다. 주어진 노드가 6,2라면 가장 가까운 조상노드는 5이므로 5를 리턴하면 된다. 이 문제는 이전에 풀었던 문제와 상당히 유사해서 금방 떠올릴 수 있었다.

 

그때는 이진검색트리의 성질을 이용해서 풀었는데 웃긴건 저번이랑 똑같이 문제를 풀었다는 점이다.

[알고리즘] LeetCode Lowest Common Ancestor of a Binary Search Tree JS

 

 

풀이

찾아야하는 노드 배열을 만든 뒤 하나하나 배열에 담으면서 탐색했다. 

쉽게 풀리긴풀렸는데 런타임, 메모리 활용도 상으로 전혀 효율적이지 못했고 시간 안에 풀지 못해 다른 사람의 풀이를 참고했다.

var lowestCommonAncestor = function (root, p, q) {
  const qArr = [];
  const pArr = [];
  const stack = [];

  const dfs = (node) => {
    if (node === null || (qArr.length > 0 && pArr.length > 0)) return;
    if (node === p) pArr.push(...stack, node);
    if (node === q) qArr.push(...stack, node);
    stack.push(node);
    dfs(node.left);
    dfs(node.right);
    stack.pop();
  };

  dfs(root);

  let prev = root;
  while (qArr.length && pArr.length) {
    const qnode = qArr.shift();
    const pnode = pArr.shift();

    if (qnode !== pnode) return prev;
    prev = qnode;
  }

  return prev;
};

 

루트에서부터 계속 탐색하는건 내가 구현한 부분과 같다. 그다음 왼쪽, 오른쪽에서 모두 발견했다면 해당 노드를 정답으로 리턴 시키면 된다.

문제는 p,q가 정답이 되는 경우였는데 다음과 같다.

테스트 케이스중 5,4가 있었는데 이때 조상노드는 5가 된다. 하지만 구현된 코드상으로 5를 찾고 끝까지 탐색하지 않기에 정답이 어떻게 리턴되는지 몰라 조금 헤맸다. 정답은 단순했는데 이진트리 왼쪽에서 5를 찾았을 때 오른쪽 노드에서 발견되면 분기가 된 root노드를 리턴하고 만약 찾지 못해서 null이 들어왔을 때는 5 아래 어딘가 있겠거니 하고 조상노드인 5를 리턴한다.

 

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  console.log(root);
  if (root) {
    if (root === p || root === q) return root;
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    if (left && right) return root;
    return left || right;
  }
  return null;
};

 

 

회고

재귀가 혼자 그리면서 구현할 때도 조금씩 헷갈려서 그냥 비슷한 유형의 문제를 많이 풀어보는 거 밖에 없는 거 같다.