[LC] 236. Lowest Common Ancestor of a Binary Tree

[seungriyou]

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

Approach

전형적인 LCA 문제. BST에 대한 LCA 문제는 #27 에서 풀어봤었다.

해당 문제와 다른 점은 BST가 아니기 때문에 모든 노드를 방문해야 한다는 점이다.

Idea 1: Recursive

1. root에서부터 left와 right에 대해 recursive 하게 내려가면서, 주어진 p와 q를 찾는다.
2. 그 과정에서 찾은 left와 right의 결과에 따라 반환한다.
   • p와 q가 각각 left와 right에 위치한다면, 현재 root가 LCA가 된다.
   • p와 q가 모두 한 쪽에 위치한다면, left와 right 중 None이 아닌 것이 LCA가 된다.

Idea 2: Iterative 💡

우선 모든 노드에 대해 부모 노드를 파악하고, p와 q 각각에서부터 root까지 올라가보면서 확인하는 것이 핵심이다.

1. BFS로 레벨 단위로 모든 노드를 순회하며 parent table을 구성한다. ({노드: 부모 노드})
2. p 부터 root 까지 올라가면서 거치는 노드를 path라는 set()에 저장한다.
3. q 부터 root 까지 올라가면서, p의 path에 속하는 노드를 마주치게 되면 멈추고 현재 노드를 반환한다.

Complexity

• Time: (recur) O(n) (모든 노드 방문) / (iter) O(n)
• Space: (recur) O(h) (트리의 높이 만큼) / (iter) O(n) (모든 노드에 대해 parent table 구성)