Leetcode - 235. Lowest Common Ancestor of a Binary Search Tree

문제

주어진 Binary Search Tree 에서 두 노드의 가장 가까운 공통 부모 (LCA)를 찾아라.

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

해결

• 현재 노드의 값이 p, q보다 작다면 LCA는 우측 자식노드에 존재. 이를 재귀적으로 반복.
• 종료조건(base case) 현재 노드 값이 p, q보다 작지도 않고, p, q보다 크지도 않는다면, 좌우 자식노드에 p또는 q가 존재한다는 논리구조이므로 해당 노드가 LCA이다.

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root->val < p->val && root->val < q->val)
            return lowestCommonAncestor(root->right, p, q);
        else if (root->val > p->val && root->val > q->val)
            return lowestCommonAncestor(root->left, p, q);
        else
            return root;
    }
};

재귀호출이아니라 loop를 사용하면 아래와 같이가능.

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (root) {
            if (root->val < p->val && root->val < q->val)
                root = root->right;
            else if (root->val > p->val && root->val > q->val)
                root = root->left;
            else
                return root;
        }
        return NULL;
    }
};