Solved using LCA(tarjan)


  • 0
    P

    class Solution {

    public:

    unordered_map<TreeNode*,TreeNode*> parent;        
    unordered_map<TreeNode*,bool> visited;
    TreeNode* left;
    TreeNode* right;
    TreeNode* ans;
    TreeNode* find(TreeNode* x){
        return parent[x]=parent[x]==x?x:find(parent[x]);
    }
    void unionset(TreeNode* x,TreeNode* y){
        TreeNode* a = parent[x];
        TreeNode* b = parent[y];
        parent[b]=a;
    }
    void LCA(TreeNode* u){
        if( u==NULL)
            return;
        parent[u]=u;
        if( u->left){
            LCA(u->left);
            unionset(u,u->left);
        }
        if( u->right){
            LCA(u->right);
            unionset(u,u->right);
        }
        visited[u]=true;
        if( u == left && visited.find(right)!=visited.end()){
            ans = find(right);
        }
        else if( u == right && visited.find(left)!=visited.end()){
            ans = find(left);
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        left = p;
        right = q;
        LCA(root);
        return ans;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.