[1스4코2파] # 205 LeetCode 235. Lowest Common Ancestor of a Binary Search Tree

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (205차)
[4코1파] 2023.01.13~ (197일차)
[1스4코1파] 2023.04.12~ (108일차)
[1스4코2파] 2023.05.03 ~ (86일차)

Today :

2023.07.28 [205일차]
tree
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/

문제 설명

이진탐색트리랑, 두 노드가 주어졌을 때, 가장 가까운 공통 부모노드(LCA)를 찾는 것이다.
여기서 LCA는 두 노드 p와 q 사이에서 p와 q를 모두 자식으로 갖는 가장 낮은 노드임. 여기서는 자기자신이 자식노드가 될 수 도 있음.

문제 풀이 방법

이진탐색트리 서성질이 각 노드의 왼쪽 서브트리는 해당 노드 값보다 작은 값이고, 오른족 서브 트리는 해당 노드 값보다 큰 값을 지닌 노드들로 이루저여있으므로, 중위순회 방식으로 확인하면서 LCA를 찾는다

내 코드

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        cur = root

        while cur:
            if p.val > cur.val and q.val > cur.val:
                cur = cur.right
            elif p.val < cur.val and q.val < cur.val:
                cur = cur.left
            else:
                return cur

증빙

여담

존나싫다