[LeetCode-Swift] 236. Lowest Common Ancestor of a Binary Tree

ref. https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
difficult. medium
time. a day
hint - O
gpt chance - O
Answer - X

목표

루트와 임의의 두 노드 p,q가 주어질 때 p와 q의 최소 공통 조상을 골라내는 문제

처음 전략

1. 각 노드의 직전 부모부터 root까지의 모든 계보를 딕셔너리에 수집
2. 딕셔너리에서 q,p만 해당하는 것을 배열로 빼냄
3. p,q의 선조들 중에서 공통되는 것의 리스트를 골라낸 후
4. root에서 가장 거리가 먼 순으로 골라냄

메모리 제한 초과가 떴음

• 그 이유는 모든 노드마다 자기 자신부터 root까지 유전 계보를 모두 저장하다 보니 메모리 제한 초과가 발생

GPT 선생님께 코드를 넘기고 어떤 문제가 있는지 여쭤봄

모든 조상을 수집하지 말고 그 노드의 바로 직전 부모만 조사하라

라고 하셔서 그렇게 코드를 수정

수정된 전략

1. 모든 노드들의 바로 직전 부모만 딕셔너리에 수집
2. p와 q가 주어지니까 타고 올라가면서 p의 모든 선조를 조사하고, q의 모든 선조를 조사
3. 배열의 앞쪽일 수록 Root에서 머니까 p의 선조 배열을 for-loop을 돌리고 당해 노드가 q의 선조 배열에도 존재하면 for-loop을 중단하고 return
   1. 필연적으로 두 노드의 공통 조상은 root

정답 코드