[Binary Tree-DFS][Medium] 236. Lowest Common Ancestor of a Binary Tree

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

Lowest Common Ancestor of a Binary Tree - LeetCode

 

Q. 주어진 root노드에서 p와 q에 동시에 부모가 되는 가장 가까운(낮은) 노드를 반환하라.

 

Solution. 

 DFS를 통해 대상 노드를 찾고 경로를 버퍼에 저장해 놓는다. 

 두 경로를 비교해서 마지막 같은 지점을 반환하면 될 것이다. 

 

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

    vBuff.push_back(node);
    if (node == target)
        return true;

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

    vBuff.pop_back();
    return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
    // 주어진 root노드에서 p와 q에 동시에 부모가 되는 가장 가까운(낮은) 노드를 반환하라.
    //
    vector<TreeNode*> vP, vQ;
    LCA_dfs(root, p, vP);
    LCA_dfs(root, q, vQ);

    int len = min(vP.size(), vQ.size());
    TreeNode* lastMatch = NULL;
    for (int q = 0; q < len; ++q)
    {
        if (vP[q] != vQ[q])
            return lastMatch;
        lastMatch = vP[q];
    }
    return lastMatch;
}

 

 

결과.