[LeetCode] 236. Lowest Common Ancestor of a Binary Search Tree

문제 출처: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Lowest Common Ancestor of a Binary Search Tree - LeetCode

 

문제

이진 탐색 트리(BST)에서, 트리 안의 두 노드의 최소 공통 조상(LCA)를 찾아라.

 

위키피디아의 LCA 정의에 따르면, "최소 공통 조상은 두 노드 p 와 q를 모두 자손 노드로 갖는 T의 가장 낮은 노드이다(자기 자신도 자손 노드로 취급한다.)."

 

예제

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6

Explanation: The LCA of nodes 2 and 8 is 6.

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2

Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Input: root = [2,1], p = 2, q = 1
Output: 2

 

풀이

이진 탐색 트리(BST)의 특성을 이용하여 재귀(혹은 반복)로 문제를 접근할 수 있다.

 

주어지는 두 노드 p와 q의 값을 기준으로 BST를 탐색해 나간다. 탐색 시에 다음과 같은 상황에 놓이게 된다.

• node.val < p.val, q.val
  • 현재 노드가 p와 q보다 작기 때문에, p와 q는 모두 현재 노드의 오른쪽 하위 트리에 있음
  • 현재 노드는 p와 q의 공통 조상이지만, LCA는 아님
  • 현재 노드의 오른쪽 하위 트리에서 다시 LCA 탐색
• node.val > p.val, q.val
  • 현재 노드가 p와 q보다 크기 때문에, p와 q는 모두 현재 노드의 왼쪽 하위 트리에 있음
  • 현재 노드는 p와 q의 공통 조상이지만, LCA는 아님
  • 현재 노드의 왼쪽 하위 트리에서 다시 LCA 탐색
• node.val == p.val 또는 node.val == q.val
  • 자기 자신 또한 후손 노드로 취급하기 때문에, 현재 노드는 LCA이다.
• q.val < node.val < p.val 또는 p.val < node.val < q.val
  • 현재 노드를 기점으로 p와 q의 위치가 갈리게 되므로, 현재 노드는 LCA이다.

위 내용을 코드로 옮기면 다음과 같다.

var lowestCommonAncestor = function(root, p, q) {
    if (root.val == p.val || root.val == q.val) { return root; }
    
    if (root.val < p.val && root.val < q.val) { return lowestCommonAncestor(root.right, p, q); }
    if (root.val > p.val && root.val > q.val) { return lowestCommonAncestor(root.left, p, q); }
    
    return root;
};

 

Github: 235.js

opwe37/Algorithm-Study