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

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

---

트리가 주어질 때, 노드 p, q의  최하위 공통조상(LCA; Lowest Common Ancestor)를 찾아라.

---

재귀함수로 풀었다.

이 함수는 탐색하는 노드를 루트로 하는 서브트리에서 p, q를 찾은경우 해당 노드를 반환하거나, 만약 두노드의 최하위 공통조상인 경우 해당 노드를 반환한다.

p, q 가 서브트리에 없는 경우는 NULL을 반환한다.

 

현재 탐색 중인 노드가 p 또는 q 인 경우 현재 노드를 반환한다.

왼쪽 자식, 오른쪽 자식들을 탐색노드로 함수를 호출한다.

왼쪽, 오른쪽 자식들에서 p, q를 찾았다면(NULL이 아니라면) 현재 탐색중인 노드가 LCA가 되므로 현재 노드를 반환한다.

오른쪽 자식노드 탐색 시 NULL을 반환하고 왼쪽 자식노드 탐색시 NULL이 아닌 값을 반환했다면 왼쪽 자식노드의 반환값을 반환한다.

오른쪽 자식노드 탐색 시 NULL을 NULL이 아닌 값을 반환하고 왼쪽 자식노드 탐색시 NULL을 반환했다면 오른쪽 자식노드의 반환값을 반환한다.

두 자식노드 탐색시 결과가 모두 NULL이라면 NULL을 반환한다.

 

시간복잡도는 트리의 노드 개수가 N인 경우 O(N)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/236.%20Lowest%20Common%20Ancestor%20of%20a%20Binary%20Tree.cpp