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

개요

이진트리와 두 개의 노드가 주어지는데 이때 두 노드 공통의 가장 가까운 조상 노드를 주어진 이진트리안에서 찾아 리턴하는 문제이다.

이때 주어진 이진트리는 BST의 속성을 가지는데 정렬되어 있다고 이해하면 된다.

 

Lowest Common Ancestor of a Binary Search Tree - LeetCode

 

풀이

사실 주어진 문제를 정확히 이해해서 풀지는 못했다.

 

단순히 DFS로 탐색하면서 지나온 노드들을 배열에 저장했다.

이후 지나왔던 배열에 대해 반복문을 돌리면서 일치하는 노드를 리턴했다

 

여기서 실수했던 부분으로는 값으로 return해야하는 부분이 TreeNode가 되어야했고 TreeNode를 넣으면 실제 비교할때도 TreeNode로 비교해야했는데 그 부분을 놓쳐 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}
 *
 * 가장 가까운 공통의 조상 노드 찾기
 */
var lowestCommonAncestor = function (root, p, q) {
  const check = [];
  const compare = [];

  function DFS(node) {
    if (node === null) return;
    else {
      // node가 들어가야한다
      check.push(node);
      //p, q도 노드였다
      if (node.val === p.val || node.val === q.val) compare.push([...check]);
      DFS(node.left);
      DFS(node.right);
      //다음 노드로 가기 위해 현재 노드를 꺼내야한다.
      check.pop();
    }
  }

  DFS(root);

  //깨내면 node가 나오니 주의
  const [x, y] = compare;

  for (let i = x.length - 1; i >= 0; i--) {
    const index = y.indexOf(x[i]);
    if (index !== -1) return x[i];
  }
};

 

Discuss

이진 탐색 트리(BST)라는 것을 놓친 부분이 구현의 복잡도를 더 늘렸다고 생각한다. 만약 이진트리안에 노드가 전부 무작위라면 맞는 방식이 되겠지만 주어진 조건을 놓쳤으니 아쉽다.

JavaScript Iterative / Recursive - LeetCode Discuss

 

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    while (root) {
        if (root.val < p.val && root.val < q.val) {
            root = root.right;
        }
        else if (root.val > p.val && root.val > q.val) {
            root = root.left;
        } else {
            break;
        }
    }
    return root;
};

bst는 정렬되어 있다고 생각하면 쉬운데 정확히는 루트 노드에 대해서 왼쪽은 루트보다 작은 노드, 오른쪽은 루트보다 큰 노드가 오는 방식으로 정렬이 된다.

 

결국 주어진 두 노드 p, q는 어디선가 조상노드에 의해 분리되게 된다. 이때 그 분리되는 루트 노드가 우리가 찾으려는 가장 가까운 조상노드이니 그 노드를 리턴하면 된다.