← 전체 회차
A-052● Day 522026.06.28mediumleetcode #235neetcode150

이진 탐색 트리의 최저 공통 조상

#tree#depth-first-search#binary-search-tree#binary-tree
↗ leetcode #235 · lowest-common-ancestor-of-a-binary-search-tree
01

문제

· problem
P.052

이진 탐색 트리의 최저 공통 조상

↗ leetcode #235

이진 탐색 트리(BST)가 주어지면, 두 개의 주어진 노드 p와 q의 최저 공통 조상(LCA) 노드를 찾으세요. 위키피디아의 LCA 정의에 따르면: "최저 공통 조상은 두 노드 p와 q 사이에서 p와 q를 모두 후손으로 가지는 T의 가장 낮은 노드로 정의됩니다(노드가 자기 자신의 후손이 될 수 있습니다)."

제약
  • · 2 ≤ number of nodes ≤ 10^5
  • · -10^9 ≤ Node.val ≤ 10^9
  • · All Node.val are unique
  • · p ≠ q and both exist in BST
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[6,2,8,0,4,7,9,null,null,3,5]
2
8
6
example 2input → output
[6,2,8,0,4,7,9,null,null,3,5]
2
4
2
example 3input → output
[2,1]
2
1
2
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    노드가 자기 자신의 후손이 될 수 있다는 것이 무엇을 의미하나요?
  • ☐
    p와 q를 찾기 위해 먼저 트리를 탐색해야 하나요?
  • ☐
    BST 성질이 LCA 찾기에 어떻게 도움이 되나요?
  • ☐
    p와 q가 다른 부분트리에 있으면 어떻게 되나요?
  • ☐
    시간 복잡도가 항상 O(log n)인가요?
  • ☐
    LCA는 항상 p 또는 q 중 하나인가요?
  • ☐
    반환된 노드가 정말 p와 q의 조상인지 검증해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 무한 반복 루프 시작
○
while True:
○
for i in range(n):
○
while root is not None:
step 2· 양쪽 노드가 우측 부분트리에 있는지 확인│ 중첩
○
if root.val < p.val and root.val < q.val:
○
if root.val <= p.val and root.val <= q.val:
○
if root.val < p.val or root.val < q.val:
○
if p.val > root.val and q.val > root.val:
step 3· 우측 부분트리로 이동│ │ 중첩
○
root = root.right
○
root = root.left
○
return root.right
○
root = root.right.right
step 4· 양쪽 노드가 좌측 부분트리에 있는지 확인│ 중첩
○
elif root.val > p.val and root.val > q.val:
○
elif root.val >= p.val and root.val >= q.val:
○
elif root.val > p.val or root.val > q.val:
○
elif p.val < root.val and q.val < root.val:
step 5· 좌측 부분트리로 이동│ │ 중첩
○
root = root.left
○
root = root.right
○
return root.left
○
root = root
step 6· 분기점이거나 조상 노드 반환│ 중첩
○
else:
○
else: return None
○
else: continue
○
else: return root.left if root.left else root.right
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, x):
4
#         self.val = x
5
#         self.left = None
6
#         self.right = None
7
8
9
class Solution:
10
    def lowestCommonAncestor(
11
        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
12
    ) -> "TreeNode":
13
        while True:
14
            if root.val < p.val and root.val < q.val:
15
                root = root.right
16
            elif root.val > p.val and root.val > q.val:
17
                root = root.left
18
            else:
19
                return root
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[6,2,8,0,4,7,9,null,null,3,5]
2
8
→
6
case 2
[6,2,8,0,4,7,9,null,null,3,5]
2
4
→
2
case 3
[2,1]
2
1
→
2
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.