[LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree (C++)

문제

 

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

Lowest Common Ancestor of a Binary Search Tree - LeetCode

 

 

풀이

 

난이도: Medium 

 

Tree에서 유명한 LCA문제.

여기서의 lower는 값이 낮다는 것이 아니라 트리에서 depth가 낮다는 의미이다. 

 

결국에는 조상을 따라가야 하는데, Leetcode의 Node는 자식 노드만 가리키므로 root로부터 node를 찾아가는 경로를 Stack 자료구조에 담는 함수를 구현하였다.

 

bool findAncestors(TreeNode* root, TreeNode* node, stack<TreeNode*>& ancestors) 

 

이 함수를 통해 p와 q로의 경로를 구하고,

두 경로는 stack으로 저장했으므로 stack의 top에는 root노드부터의 조상 경로가 저장이 되어있다.

따라서 p와 q의 경로가 달라지는 시점의 직전 노드가 LCA가 된다.

 

코드

 

 

 

 

또는 p와 q의 경로를 따로 찾지 않아도, 결국 같은 조상만 탐색해 내려오다가 서로 분기가 갈리는 시점에 LCA를 찾는 간단한 방법도 있다.

 

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/solutions/3724176/easy-to-understand-c-solution-recursive-o-logn/