Massive Algorithms: LCA

Showing posts with label LCA. Show all posts

LCA of Deepest Nodes in Binary Tree - Facebook

https://www.cnblogs.com/EdwardLiu/p/6551606.html

给一个 二叉树 ， 求最深节点的最小公共父节点
     1
  2   3
     5  6    return 3.

       1  
    2   3
4      5 6   retrun 1. 
先用 recursive  ， 很快写出来了， 要求用 iterative 。 时间不够了。。。

Recursion: 返回的时候返回lca和depth，每个node如果有大于一个子节点的depth相同就返回这个node，如果有一个子节点depth更深就返回个子节点lca，这个o(n)就可以了

Iteration: tree的recursion换成iteration处理，一般用stack都能解决吧（相当于手动用stack模拟recursion）。感觉这题可以是一个样的做法，换成post order访问，这样处理每个node的时候，左右孩子的信息都有了，而且最后一个处理的node一定是tree root

我的想法是要用hashMap<TreeNode, Info>

class Info{

　　int height;

　　TreeNode LCA;

}

 5     private class ReturnVal {
 6         public int depth;   //The depth of the deepest leaves on the current subtree
 7         public TreeNode lca;//The lca of the deepest leaves on the current subtree
 8 
 9         public ReturnVal(int d, TreeNode n) {
10             depth = d;
11             lca = n;
12         }
13     }
14 
15     public TreeNode LowestCommonAncestorOfDeepestLeaves(TreeNode root) {
16         ReturnVal res = find(root);
17         return res.lca;
18     }
19 
20     private ReturnVal find(TreeNode root) {
21         if(root == null) {
22             return new ReturnVal(0, null);
23         } else {
24             ReturnVal lRes = find(root.left);
25             ReturnVal rRes = find(root.right);
26 
27             if(lRes.depth == rRes.depth) {
28                 return new ReturnVal(lRes.depth+1, root);
29             } else {
30                 return new ReturnVal(Math.max(rRes.depth, lRes.depth)+1, rRes.depth>lRes.depth?rRes.lca:lRes.lca);
31             }
32         }
33     }

find lowest common ancestor among deepest nodes in k-nary tree
前⼏几年年的经典题

Family Relation

亲戚
第二轮：自己定义数据结构，找出两个人是否是亲戚，follow up是如何测试。

https://www.1point3acres.com/bbs ... read&tid=492150

如果只判断两人，似乎DFS就可以了。
如果是判断任意两人，union find 可否？如果是亲戚的节点就肯定都是亲戚了。大嫂的二姑的三姨的四表舅的五儿子的六姑妈的七大爷

没想明白的是亲戚的关系有血缘和结婚两种吧？如果followup问任意两人是血缘关系还能用UF吗？比如除了一个general的parent，还保留一个血缘的parent。当加入的edge是血缘关系和婚姻关系的时候对这两个parent做不同处理。

union find没什么毛病. lca也可以

（一夫一妻制，不允许图中P又和其他人生小孩）
如何判断E和H是否related ==> true
followup
孩子的基因是一半母亲，一半父亲。
判断E和H血缘有多少match ==> 50%
A和B血缘match ==> 100%

https://www.1point3acres.com/bbs ... read&tid=488670

Who is our Boss? LCA for n-array Tree - Algorithms and Problem SolvingAlgorithms and Problem Solving

Who is our Boss? LCA for n-array Tree - Algorithms and Problem SolvingAlgorithms and Problem Solving
In a company which has CEO Bill and a hierarchy of employees. Employees can have a list of other employees reporting to them, which can themselves have reports, and so on. An employee with at least one report is called a manager.
Please implement the closestCommonManager method to find the closest manager (i.e. farthest from the CEO) to two employees. You may assume that all employees eventually report up to the CEO.

public static Employee closestCommonManager(Employee ceo, Employee firstEmployee, Employee secondEmployee) {
 Stack<Employee> firstPath = new Stack<Employee>();
 Stack<Employee> secondPath = new Stack<Employee>();
 
 Employee root = ceo;
 
 DFS(root, firstEmployee, firstPath);
 DFS(root, secondEmployee, secondPath);
 
 if(firstPath.peek().getId() == firstEmployee.getId() && secondPath.peek().getId() == secondEmployee.getId()){
  int size1 = firstPath.size();
  int size2 = secondPath.size();
  int diff = Math.abs(size2-size1);
  
  if(size1 > size2){
   moveUp(firstPath, diff);
  }
  else{
   moveUp(secondPath, diff);
  }
  
  while(firstPath.peek().getId() != secondPath.peek().getId()){
   firstPath.pop();
   secondPath.pop();
  }
  
  if(firstPath.size() > 0){
   return firstPath.pop();
  }
 }
    return null;
}

private static boolean DFS(Employee root, Employee target, Stack<Employee> path){
 path.push(root);
 if(root.getId() == target.getId()){
  return true;
 }
 
 for(Employee r : root.getReports()){
  boolean res = DFS(r, target, path);
  if(res){
   return true;
  }
 }
 
 path.pop();
 
 return false;
}

private static void moveUp(Stack<Employee> path, int diff){
 while(diff > 0 && !path.isEmpty()){
  path.pop();
  diff--;
 }
}

Read full article from Who is our Boss? LCA for n-array Tree - Algorithms and Problem SolvingAlgorithms and Problem Solving

Modified Lowest Common Ancestor | CODING INTERVIEW ARCHIVES

Modified Lowest Common Ancestor | CODING INTERVIEW ARCHIVES
The lowest common ancestor(LCA) between two nodes a and b is defined as the lowest node in tree T that has both a and b as descendants (where we allow a node to be a descendant of itself).
The problem here is to find the LCA of 2 nodes, in such a way that a given node is not allowed to be a descendant of itself. Hence, if any of the 2 nodes is the root of the tree then the LCA does not exist.

Approach:
To find the LCA, we follow a recursive approach. If the root has value equal to any of a or b, we return the root.
We recursively find the nodes in the left subtree and the right subtree.
If both the subtree respectively have 1 of the 2 given nodes, we return the root.
Else, if any one of the 2 return values is not NULL, return that value (It means atleast 1 of the nodes is found in that tree).
Else, return NULL (It means none of the 2 nodes is found in the subtrees).
The base case is to return NULL for a NULL root.

Now, for the modified LCA problem, instead of checking the value of root to be equal to one of the given values a or b, we check if any of the value a or b is equal to the value of any of the 2 child of root node.
This is done only if the corresponding child of the root exists. Thus, the base case can be to return NULL if none of the child exists(i.e. the root is a leaf).
Other conditions and the code remains the same.
// Function to build a sample tree from given
// inorder and preorder traversals
Node treeFromInAndPre(int *in,int *pre,int lb,int ub,int *idx){
if(lb>ub)
return NULL;
int i=lb;
while(in[i]!=pre[*idx])
i++;
Node root=getNode(pre[*idx]);
(*idx)++;
root->left=treeFromInAndPre(in,pre,lb,i-1,idx);
root->right=treeFromInAndPre(in,pre,i+1,ub,idx);
return root;

}
// function to get LCA
Node getLCA(Node root,int a,int b){
if(!root)
return NULL;
if(root->data==a || root->data==b)
return root;
Node left=getLCA(root->left,a,b);
Node right=getLCA(root->right,a,b);
if(left && right) return root;
else if(left) return left;
else return right;
}
// function to get LCA according to the
// modified definition
Node getLCA_Modified(Node root,int a,int b){
if(!root || root->data==a || root->data==b)
return NULL;
if(!root->left && !root->right)
return NULL;
if(root->left){
if(root->left->data == a || root->left->data == b)
return root;
}
if(root->right){
if(root->right->data == a || root->right->data == b)
return root;
}
Node left=getLCA_Modified(root->left,a,b);
Node right=getLCA_Modified(root->right,a,b);
if(left && right) return root;
else if(left) return left;
else return right;

}
Read full article from Modified Lowest Common Ancestor | CODING INTERVIEW ARCHIVES

Node to Node Binary Tree Path

http://segmentfault.com/a/1190000003465753
给定一棵二叉树的根节点和两个任意节点，返回这两个节点之间的最短路径

时间 O(h) 空间 O(h) 递归栈空间

两个节点之间的最短路径一定会经过两个节点的最小公共祖先，所以我们可以用LCA的解法。不同于LCA的是，我们返回不只是标记，而要返回从目标结点递归回当前节点的路径。当遇到最小公共祖先的时候便合并路径。需要注意的是，我们要单独处理目标节点自身是最小公共祖先的情况。

public LinkedList<TreeNode> helper(TreeNode n, TreeNode p, TreeNode q){
    if(n == null){
        return null;
    }
    
    LinkedList<TreeNode> left = helper(n.left, p, q);
    LinkedList<TreeNode> right = helper(n.right, p, q);
    
    // 当左右都为空时
    if(left == null && right == null){
        // 如果当前节点是目标节点，开启一条新路径
        if(n == p || n == q){
            LinkedList l = new LinkedList<TreeNode>();
            l.add(n);
            return l;
        } else {
        // 否则标记为空
            return null;
        }
    // 如果左右节点都不为空，说明是最小公共祖先节点，合并两条路径
    } else if(left != null && right != null){
        finalPath.addAll(left);
        finalPath.add(n);
        Collections.reverse(right);
        finalPath.addAll(right);
        return left;
    // 如果当前节点是目标结点，且某一个子树不为空时，说明最小公共祖先是节点自身
    } else if (left != null){
        left.add(n);
        if(n == p || n == q){
            finalPath.addAll(left);
        }
        return left;
    } else {
        right.add(n);
        if(n == p || n == q){
            finalPath.addAll(right);
        }
        return right;
    }
}

LCA问题的跳表算法 >> NoAlGo博客

LCA问题的跳表算法 » NoAlGo博客
LCA问题的一般形式：给定一棵有根树，给出若干个查询，每个查询要求指定节点u和v的最近公共祖先。
LCA问题有两类解决思路:

在线算法，每次读入一个查询，处理这个查询，给出答案。
离线算法，一次性读入所有查询，统一进行处理，给出所有答案

跳表算法是在线算法，其需要O(nlogn)的复杂度进行初始化，然后每进行一个查询需要O(logn)复杂度进行解答。

使用跳表解决LCA问题时，对每个节点i维护了一个数组anc[i][j]，表示i的第2^j个祖先的节点。有了这个数组后，节点x沿着树往上跳2^k层之后，就变成了节点anc[x][k]。当待查询的两个节点u和v在同一层时，我们把uv每次向上跳2的幂次的距离，最后同时到达了u和v的LCA节点。

可以知道，由于每次跳的距离都是2的幂，如果把uv和其LCA节点间的深度差用二进制表示，则其中的每个出现1的位置就是uv每次所要跳的距离。比如，要查找5和6的LCA，则把5和6都往上跳2^1层，同时到达0，0即为所求LCA。

但如果0上面还有很多节点，则5和6同时往上跳比2更大的距离（如4）时，也会到达同样的节点，但并不是LCA（不是最近）。

为了避免这个问题，我们在跳的时候不要让他们到达相同的节点，这样就不会跳过头了。最终u和v会跳到其LCA的下一层，u和v的父亲就是他们的LCA。即，查找5和6的LCA时，5最终会跳到1，6会跳到3，它们的父亲0为要求的LCA。

当待查询的两个节点u和v不在同一层时，假如u的层数比较深。这是我们先把u跳到和v同一层的祖先中，然后再使用上述相同层的方法。把u每次往上跳2的幂次的层数，如果跳了之后在v的上方了，则不跳，否则就跳。可以知道，将u和v之间的深度差用二进制表示，则其中每个出现1的位置就是要跳的距离。比如，要查找7和6的LCA，首先把7往上跳到和6同一层的5中，然后再使用上述方法求5和6的LCA即可。

Read full article from LCA问题的跳表算法 » NoAlGo博客

Online LCA - Using RMQ

LCA与RMQ互相转化 » NoAlGo博客
http://www.zhihu.com/question/19957473
2. O(n log n) 预处理 + O(1) 查询的在线LCA算法
这个算法不要求事先知道所有查询。来一个查询就处理一个，每处理一个复杂度是常数。其思想是将LCA问题转化成RMQ(Range Minimum/Maximum Query)，然后再利用高效的RMQ算法如线段树，Sparse Table 等求解。对于RMQ问题，如果要追求O(1)的查询复杂度，就不能用线段树了（线段树是O(log n)的），所以可以采用基于动态规划的Sparse Table方法。

(1)将LCA 转化成RMQ:
对于有n个节点的树，我们先建三个一维数组: First[0...n], Depth[0...2*n], Seq[0, 2*n]（稍后解释这三个数组的意义）。然后DFS这棵树，传统的打印DFS序列的流程如下：

function DFS(u)
     u.visit = true
     print u.id
     foreach child v of u
          if v.visit == false
              dfs(v)
          end
     end
end

我们将上述流程修改一下：

function DFS(u)
     u.visit = true
     print u.id
     foreach child v of u
         if v.visit == false
             dfs(v)
         end
         print u.id
     end
end

也就是在每次回溯时我们也把节点u打印一下。可以证明这时的dfs序列长度是2*n-1（传统dfs序列的长度是n

LCA转RMQ主要是通过DFS（深度优先搜索）完成，时间复杂度为O(n)。
DFS时每次进入以及回溯到某一个节点时，我们都记录访问到的节点val，同时记录下这个节点的深度depth。因为进入及回溯时都要记录，所以一个节点可能会被记录多次。另外，为了后面应用RMQ的方便，还使用数组first记录每个元素第一次访问的下标。
http://blog.csdn.net/smallacmer/article/details/7432664
LCA与RMQ问题的转化，LCA问题可以经过DFS+st变成rmq（min）的解法，而且求解的时间复杂度规模是一样的.

DFS时每次进入以及回溯到某一个节点时，我们都记录访问到的节点val，同时记录下这个节点的深度depth。因为进入及回溯时都要记录，所以一个节点可能会被记录多次。另外，为了后面应用RMQ的方便，还使用数组first记录每个元素第一次访问的下标。

例如，下面是一棵以节点0为根节点的多叉树：

以这棵树为例，我们进行DFS时可以得到如下depth数组和val数组：

val	0	1	4	1	5	7	5	1	0	2	0	3	6	3	0
depth	0	1	2	1	2	3	2	1	0	1	0	1	2	1	0

first数组为

下标	0	1	2	3	4	5	6	7
值	0	1	9	11	2	4	12	5

要求x和y的LCA时，因为LCA的深度肯定是最小的，于是可以通过first数组找到x和y首次出现的位置first[x]和first[y]，然后再depth数组查找从first[x]到first[y]的RMQ的下标id，然后在val数组中找到下标id所代表的元素，即为x和y的LCA。

即 LCA(x, y) = val[RMQ(depth, first[x], first[y])]

int depth[mx], val[mx], first[mx];
int id; //记录当前数组的长度
void dfs(int x, int dep)
{
 depth[id] = dep; val[id] = x; first[x] = id; id++;
 for (int i = 0; i < tree[x].size(); i++)
 {
  dfs(tree[x][i], dep+1);
  depth[id] = dep; val[id] = x; id++; //递归完一棵子树回到自身
 }
}

https://gist.github.com/ddrone/2975702
Implementation of online static RMQ-problem with O(N) preprocessing time and O(1) query time Raw

http://kmplayer.iteye.com/blog/604232

struct node //可以添加额外的信息
{
int v;//孩子结点
};
//注意vector在树问题中的使用
vector<node> tree[maxn];
int dfsnum[maxn]; //记录遍历的节点
int depth[maxn]; //记录节点对应的深度
int first[maxn]; //记录结点第一次访问到时的下标
int top; //记录总的步伐数
void dfs(int m,int f,int dep) //当前节点编号,父节点编号,深度
{
dfsnum[top]=m;
depth[top]=dep;
first[m]=top;
top++;
for(unsigned i=0;i<tree[m].size();i++)
{
if(tree[m][i].v==f)
continue;
dfs(tree[m][i].v,m,dep+1);
dfsnum[top]=m; //注:每条边回溯一次,所以top的值=n+n-1
depth[top]=dep;
top++;
}
}
int dp[maxn][18];
void makeRmqIndex(int n,int b[]) //返回最小值对应的下标
{
int i,j;
for(i=0;i<n;i++)
dp[i][0]=i;
for(j=1;(1<<j)<=n;j++)
for(i=0;i+(1<<j)-1<n;i++)
dp[i][j]=b[dp[i][j-1]] < b[dp[i+(1<<(j-1))][j-1]]? dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
}
int rmqIndex(int s,int v,int b[])
{
int k=(int)(log((v-s+1)*1.0)/log(2.0));
return b[dp[s][k]]<b[dp[v-(1<<k)+1][k]]? dp[s][k]:dp[v-(1<<k)+1][k];
}
int lca(int x,int y)
{
return dfsnum[rmqIndex(first[x],first[y],depth)];
}
int main()
{
int n=5;//顶点数
top=0;
//分别存放每条边的端点
int x[]={1,1,3,3};
int y[]={2,3,4,5};
node temp;
for(int i=0;i<n-1;i++) //n-1条边
{
temp.v=y[i];
tree[x[i]].push_back(temp);
temp.v=x[i];
tree[y[i]].push_back(temp);
}
dfs(1,-1,0); //根节点为1
cout<<"总数:"<<top<<endl;
makeRmqIndex(top,depth);
cout<<"lca(4,5):"<<lca(4,5)<<endl;

http://www.codeproject.com/Articles/141999/Solving-LCA-by-Reducing-to-RMQ-in-C
Read full article from LCA与RMQ互相转化 » NoAlGo博客