[Leetcode 아주 상세한 문제풀이] 235. Lowest Common Ancestor of a Binary Search Tree – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 235번 문제 Lowest Common Ancestor of a Binary Search Tree 다.

우선 문제를 살펴보자.

 

리트코드 235번 문제 Lowest Common Ancestor of a Binary Search Tree 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

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.

 

 

문제 설명

문제를 간략히 살펴보자. 인풋으로 binary search tree (BST)가 주어진다. 동시에 BST 안에 존재하는 두 개의 노드값이 주어진다. 이때 인풋으로 주어진 두 노드의 lowest common ancestor (LCA)를 구하라는 것이다. 이해를 돕기 위해 용어부터 설명하면 ancestor는 조상이라는 뜻이다. Binary tree에서 조상이라 함은 tree 구조의 위쪽을 의미한다. 즉, 문제에서 요구하는 바는 인풋으로 주어진 두 개의 노드에 대하여 공통되는 상위 노드 중 가장 낮은 노드를 찾으라는 것이다.

문제 예시 2번을 살펴보자. BST와 두 개의 노드값 2와 4가 인풋으로 주어졌다. 이때 노드 2와 4의 공통 조상 노드를 찾아내야 한다. Binary tree 구조에서 알 수 있듯이 노드 2와 4를 품는 노드 중 가장 아래 있는 노드는 2가 된다. 이때 2는 자기 자신이 조상 노드가 될 수 있는데 이는 노드 2가 노드 4를 child로 품기 때문이다. 만약 이 문제 예시에서 노드 0과 노드 5의 공통 조상을 찾는 경우 역시 노드 2가 가장 낮은 공통 조상 노드가 된다. 말로 이해하는 것이 어렵다면 binary tree 구조를 직접 그려본다면 이해하는데 좀 더 도움이 될 것이다. 이제 문제를 풀어보자.

 

 

문제 접근법

이 문제를 해결하기 위해서는 Binary Search Tree의 성질에 대한 이해가 필요하다.

BST의 경우 특정 root 노드 n에 대해 왼쪽 subtree의 노드들은 n 보다 작은 값을 갖고,

오른쪽 subtree의 노드들은 n 보다 큰 값을 갖는 특성을 지닌다.

BST의 이러한 특성을 상기하며 인풋으로 주어진 두 노드 p와 q의 위치를 생각해 보자.

우리는 특정 root 노드를 기준으로 노드 p와 q의 위치에 대해 3가지 경우가 있음을 알 수 있다.

1) 특정 root 노드를 기준으로 다른쪽에 위치한 경우

- 만약 p와 q가 특정 root 노드를 기준으로 다른쪽에 있다면 그 root 노드가 우리가 찾고자 하는 LCA다. 그 이유는 노드 p와 q부터 시작해 root 노드로 올라갈 때 그 root 노드가 교차점이 되기 때문이다.

2) 특정 root 노드를 기준으로 같은쪽에 위치한 경우

- 만약 p와 q가 root 노드보다 크다면 p와 q 모두 오른쪽 subtree에 위치힌다. 따라서 LCA도 오른쪽 subtree에 위치한다.

- 만약 p와 q가 root 노드보다 작다면 p와 q 모두 왼쪽 subtree에 위치힌다. 따라서 LCA도 왼쪽 subtree에 위치한다.

위 두 가지 경우 우리는 tree의 아래쪽으로 탐색을 계속하면 된다. 1) 경우에서 처럼 특정 root 노드를 기준으로 p와 q가 다른쪽에 위치한 경우를 찾을때까지 탐색을 계속한다.

3) p와 q 중 하나가 root 노드일 때

- 이 경우 LCA의 정의에 따라 그 root 노드가 LCA가 된다. p와 q중 하나가 root 노드이고 다른 노드가 root 노드에 속하기 때문에 결국 교차점은 그 root 노드가 되기 때문이다.

우리는 BST를 탐색하며 위 3가지 경우를 판단해 인풋으로 주어진 p와 q 노드에 대한 LCA를 찾을 수 있다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

Binary tree를 표현하기 위한 class를 선언해준다. (line 1-5)

이는 파이썬에서 일반적으로 사용되는 표현식이니 익숙해 지도록 하자.

Binary tree를 이루는 노드값과 p, q 값을 입력받기 위한 함수를 정의해 준다. (line 7)

만약 입력받은 binary tree가 비어있다면 none을 리턴하고 종료한다. (line 8-9)

첫번째로 p와 q가 root 노드보다 큰지 판단한다. (line 12)

이 경우 앞서 설명한대로 LCA가 오른쪽 subtree에 존재함을 의미한다.

따라서 오른쪽 subtree의 root를 기준으로 하는 새로운 탐색을 재귀 함수를 이용하여 진행한다. (line 13)

두번째로 p와 q가 root 노드보다 작은지 판단한다. (line 16)

이 경우 앞서 설한대로 LCA가 왼쪽 subtree에 존재함을 의미한다.

따라서 쪽 subtree의 root를 기준으로 하는 새로운 탐색을 재귀 함수를 이용하여 진행한다. (line 17)

위 두 경우가 아니라면 p와 q가 서로 다른 subtree에 존재하거나 혹은 둘 중 하나가 root인 경우다. (line 21)

따라서 이 경우 위에서 설명한대로 탐색하고 있는 root가 LCA가 되므로 root 를 리턴한다. (line 22)

 

 

문제 풀이 코드

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def lowestCommonAncestor(root, p, q):
    if root is None:
        return None
 
    # If both p and q are greater than root, then LCA lies in right subtree
    if p.val > root.val and q.val > root.val:
        return lowestCommonAncestor(root.right, p, q)
 
    # If both p and q are lesser than root, then LCA lies in left subtree
    elif p.val < root.val and q.val < root.val:
        return lowestCommonAncestor(root.left, p, q)
 
    # If one of p or q is on one side of root and the other is on the other side,
    # then root is the LCA
    else:
        return root
 
# Helper function to build a tree from a list
def buildTree(lst, root, i, n):
    if i < n:
        temp = TreeNode(lst[i])
        root = temp
 
        # insert left child
        root.left = buildTree(lst, root.left, 2 * i + 1, n)
 
        # insert right child
        root.right = buildTree(lst, root.right, 2 * i + 2, n)
    return root
 
# Example usage
lst = [6,2,8,0,4,7,9,None,None,3,5]
root = buildTree(lst, None, 0, len(lst))
p = TreeNode(2)
q = TreeNode(8)
 
ancestor = lowestCommonAncestor(root, p, q)
print("LCA:", ancestor.val if ancestor else "None")
 

 

 

관련 문제

리트코드 98번 Validate binary search tree 문제 풀이 (링크)

리트코드 102번 Binary tree level order traversal 문제 풀이 (링크)

리트코드 104번 Maximum depth of binary tree 문제 풀이 (링크)

리트코드 105번 Construct binary tree from preoder and inorder traversal 문제 풀이 (링크)

리트코드 124번 Binary tree maximum path sum 문제 풀이 (링크)

리트코드 208번 Implement tree (Prefix tree) 문제 풀이 (링크)

리트코드 212번 Word search 2 문제 풀이 (링크)

리트코드 226번 Invert/flip binary tree 문제 풀이 (링크)

리트코드 572번 Subtree of another tree 문제 풀이 (링크)

 

235. Lowest Common Ancestor of a Binary Search Tree