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

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

 

주어진 트리에서 두개의 target 노드 중, 가장 낮은 위치의 공통 부모 노드를 찾아라.

 

특정 노드간의 경로를 우선 기록한다. 

그리고 두 노드 경로를 비교해서 달라지기 시작하면, 그 바로 직전 노드가 가장 낮은 공통 부모다.

 

 

코드.

bool collectPathToNode(TreeNode* node, TreeNode* target, vector<TreeNode*>& vBuff)
{
    if (node == nullptr)
        return false;

    vBuff.push_back(node);

    if (node == target)
        return true;

    if (collectPathToNode(node->left, target, vBuff) || collectPathToNode(node->right, target, vBuff))
        return true;

    vBuff.pop_back();
    return false;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
{
    vector<TreeNode*> vPathP, vPathQ;
    collectPathToNode(root, p, vPathP);
    collectPathToNode(root, q, vPathQ);

    TreeNode* ret = nullptr;
    int count = min(vPathP.size(), vPathQ.size());
    for(int k = 0; k < count ; ++k)
    {
        if (vPathP[k] != vPathQ[k])
            return ret;
        else
            ret = vPathP[k];
    }
    return ret;    
}

 

 

결과