[Grind75-LeetCode] Lowest Common Ancestor of a Binary Search Tree JAVA

반응형

728x90

[Grind75-Leetcode] Lowest Common Ancestor of a Binary Search Tree - Easy

---

접근

• 재귀

---

풀이

Grind75에 있는 leetcode 문제인 최저 공통 조상 노드?를 찾는 문제이다. 위키백과의 정의에 따르면 최저 공통 조상은 두 노드 p와 q에 대해, p와 q를 자식으로 가지는 T의 가장 낮은 노드로 정의된다고 한다. 그리고 노드가 자기 자신을 자식으로 가질 수 있다고 한다. 이 말은 뒤에서 설명하겠다.

 

아무튼 주어지는 이진 탐색 트리 구조를 가지고 p노드와 q노드의 최저 공통 조상 노드가 무엇인지 찾으면 되는데 이진 탐색 트리의 특성상 왼쪽 서브 트리의 모든 자식 노드는 루트 노드보다 값이 작고 오른쪽 서브 트리의 모든 자식 노드는 루트 노드보다 값이 큰 성질을 이용해 탐색을 진행하면 된다. 루트 노드부터 입력받는 p와 q의 값을 비교하여 루트 노드보다 크다면 오른쪽 서브 트리를 탐색하고 작다면 왼쪽 서브 트리를 탐색하면서 해당 노드가 나올 때까지 진행하면 된다. 

출처: leetcode

해당 문제에 주어지는 예시 트리 구조이다. 예시로 주어지는 값이 p=2, q=4라면 루트 노드인 6과 비교해 탐색을 시작하는 것이다. 해당 문제의 종료 조건은 p와 q가 서로 다른 서브 트리에 위치하는 경우로 root 값 보다 한쪽은 작고 한쪽은 크거나 자기 자신을 자식으로 가질 때이다. 자기 자신을 자식으로 가진 다는 것은 값이 루트를 기준으로 꼭 양쪽으로 갈라지지 않고 두 값 중 하나가 루트의 값과 동일해도 된다는 뜻이다. 

p = 2, q = 4, root = 6

p < root -> 왼쪽 서브트리 탐색
q < root -> 왼쪽 서브트리 탐색

새로운 root = 2

p == root, q > root 
한쪽이 같아도 종료 -> 노드가 자신을 자식으로 가질 수 있음

결과 = 2

위에 해당하는 경우를 다 찾으면 되는데 재귀를 이용해 간단하게 풀 수 있다.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

이번 문제에 사용되는 TreeNode 구조로 해당 노드의 값, 왼쪽 오른쪽 서브트리 루트 노드 그리고 노드 값을 받는 생성자 하나로 이루어져 있다.

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int rootVal = root.val;

        if (p.val < rootVal && q.val < rootVal) {
            return lowestCommonAncestor(root.left, p, q);
        }

        else if (p.val > rootVal && q.val > rootVal) {
            return lowestCommonAncestor(root.right, p, q);
        }

        else {
            return root;
        }
    }

코드가 짧아서 통째로 가져왔다. root 노드의 값을 기준으로 비교를 하고 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) {
        int rootVal = root.val;

        if (p.val < rootVal && q.val < rootVal) {
            return lowestCommonAncestor(root.left, p, q);
        }

        else if (p.val > rootVal && q.val > rootVal) {
            return lowestCommonAncestor(root.right, p, q);
        }

        else {
            return root;
        }
    }
}

여기 사이트의 문제들은 접근 자체를 좀 더 알고리즘 원리에 가깝게 하도록 강제 되어있어 타 사이트들보다 공부하기엔 더 좋은 거 같다.