[Leetcode] 235. Lowest Common Ancestor of a Binary Search Tree

Identifying the Problem

BST Tree 내의 p와 q의 공통 조상을 찾아 리턴한다.

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6

Explanation: 2와 8의 공통 조상은 6이다.

Organizing thoughts

##아이디어 참고 및 출처

C++ Recursive and Iterative - LeetCode Discuss

먼저 가능한 경우의 수를 정리해보자 

아래는  p, q가 root기준으로 위치한 곳에 따른 리턴 값이다.

p	q	return
왼쪽	왼쪽	왼쪽 어딘가
왼쪽	오른쪽	root
오른쪽	오른쪽	오른쪽 어딘가

즉 다음과 같은 경우가 됐을 때, 왼쪽 어딘가 혹은 오른쪽 어딘가를 전위순회로 탐색하다,

왼쪽 p 오른쪽 q가 되는 경우 또는 그 외의 경우

(q의 왼쪽 자손 노드가 p인 경우 or p의 오른쪽 자손 노드가 q인 경우)

root를 return 한다.

Sourcecode

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if(root->val > p->val && root->val > q->val) //둘 다 왼쪽
            return lowestCommonAncestor(root->left, p, q); 
        if(root->val < p->val && root->val < q->val) //둘 다 오른쪽
            return lowestCommonAncestor(root->right, p, q);
        return root; //그 이외의 경우 root 리턴
    }
};