[LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree - Java

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

Lowest Common Ancestor of a Binary Search Tree - LeetCode

---

문제

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

 

Example 1:

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.

Example 2:

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.

Example 3:

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

 

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q will exist in the BST.

---

풀이

풀이 과정

이진 탐색트리 root와 노드 p, q가 주어졌을 때 노드 p와 q의 최소 공통 조상을 찾는 문제이다. (각 노드는 자신 역시 조상으로 간주한다)

이진 탐색 트리에서 세 노드에 대해서 비교할 때 크게 네가지 경우를 생각해 볼 수 있다.

1. p와 q의 값이 root를 기준으로 양쪽으로 나누어져 있는 경우
2. root의 값이 p나 q의 값 중 하나와 같은 경우
3. p와 q의 값이 모두 root보다 작은 경우
4. p와 q의 값이 모두 root보다 큰 경우

먼저 p와 q의 값이 root를 기준으로 양쪽으로 나누어져 있는 경우 왼쪽/오른쪽 서브트리에서는 공통 조상이 존재할 수 없으므로 root가 최소 공통 조상이 된다

// p와 q의 값이 root를 기준으로 양쪽으로 퍼져있을 경우 root가 최소 공통 조상이 됨
if((root.val > p.val && root.val < q.val) || (root.val > q.val && root.val < p.val)) return root;

 

두 번째로 root의 값이 p나 q의 값 중 하나와 같은 경우, 즉 p나 q중 하나가 그 자체로 본인의 조상으로 간주되는 경우 역시 root가 최소 공통 조상이 된다.

// root의 값이 p나 q의 값 중 하나와 같다면 역시 root가 최소 공통 조상이 됨
if(root.val == p.val || root.val == q.val) return root;

 

세 번째로 p와 q의 값이 모두 root보다 작은 경우 p와 q 모두 root의 왼쪽 서브트리에 존재하게 된다. 그러나 최소 공통조상이 무엇인지는 아직 알 수 없으므로 위의 두 가지 경우가 나올 때 까지 왼쪽 서브트리를 재귀 탐색한다.

// p와 q가 root보다 작은 경우 왼쪽 서브트리를 탐색
if(p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);

 

마지막으로 p와 q의 값이 모두 root보다 큰 경우 p와 q모두 오른쪽 서브트리에 존재하며 역시 최소 공통 조상은 알 수 없다. 따라서 세 번째 경우와 마찬가지로 1, 2번 경우가 나올 때 까지 오른쪽 서브트리를 재귀탐색한다.

// 나머지 경우, p와 q가 root보다 큰 경우 오른쪽 서브트리를 탐색
return lowestCommonAncestor(root.right, p, q);

---

최종 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // p와 q의 값이 root를 기준으로 양쪽으로 퍼져있을 경우 root가 최소 공통 조상이 됨
        if((root.val > p.val && root.val < q.val) || (root.val > q.val && root.val < p.val)) return root;
        // root의 값이 p나 q의 값 중 하나와 같다면 역시 root가 최소 공통 조상이 됨
        if(root.val == p.val || root.val == q.val) return root;
        // p와 q가 root보다 작은 경우 왼쪽 서브트리를 탐색
        if(p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
        // 나머지 경우, p와 q가 root보다 큰 경우 오른쪽 서브트리를 탐색
        return lowestCommonAncestor(root.right, p, q);
    }
}

---