LeetCode 235(Lowest Common Ancestor of a Binary Search Tree, java)

0. 문제

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

Lowest Common Ancestor of a Binary Search Tree - LeetCode

 

1. 문제 설명

- 문제에서 이진 탐색 트리(root)와 두 개의 노드(p, q)가 주어진다.

- 주어진 두 개의 노드(p, q) 사이에 존재하는 노드 중 가장 작은 값을 가지는 노드(LCA)를 찾는 것이 문제의 핵심이다.

- 두 노드 사이에 존재하는 노드란, 상위 노드(= ancestor)를 의미한다. 

 

- 여기서 LCA는 Lowest Common Ancestor의 약어다.

- LCA는 문제에서 주어진 두 개의 노드(p, q)를 자식 노드로 갖는다.

- 중요한 점은 모든 노드는 스스로를 자식 노드라고 판단할 수 있다.

- 그러므로 문제에서 주어진 두 개의 노드(p, q) 중 하나는 상위 노드일 수 있다는 것이 판단의 요인이다. 

  

2. 문제 해설

a) 첫 번째 접근

- 우선 주어진 두 개의 노드(p, q)가 어떤 노드의 자식 노드인지를 파악한다.

 

- 만약 두 노드가 모두 어떤 노드의 자식 노드인 경우에는 다음 두 가지 조건에 부합한다.

   → 주어진 두 개의 노드(p, q)가 모두 루트 노드보다 큰 값을 가진다면 우측 탐색을 진행한다.

   → 반대로 주어진 두 개의 노드(p, q)가 모두 루트 노드보다 작은 값을 가진다면 좌측 탐색을 진행한다.

 

- 위의 두 가지 조건에 기반하여 트리를 탐색한다.

 

b) 두 번째 접근

- 위의 두 가지 조건에 부합하지 않는 경우는 다음 2가지 케이스로 구분할 수 있다. 

  → 두 노드(p, q)가 모두 현재 위치의 노드를 상위 노드로 갖는 경우(= 현재 탐색된 노드의 자식 노드인 경우)

  → 두 노드(p, q) 중 하나가 상위 노드인 경우

 

- 이 두 가지 케이스는 상위 노드를 반환하는 케이스이므로 상위 노드를 반환한다.

 

- 이제 위의 조건을 재귀 함수로 구현하면 끝이다.

- 다음 코드를 보면서 이해해보자.  

 

3. 정답 코드

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        if(root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        
        else if(root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        
        else {
            return root;
        }
    }
}