/**
* Definition of ParentTreeNode:
*
* class ParentTreeNode {
* public ParentTreeNode parent, left, right;
* }
*/
public class Solution {
/*
* @param root: The root of the tree
* @param A: node in the tree
* @param B: node in the tree
* @return: The lowest common ancestor of A and B
*/
public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root, ParentTreeNode A, ParentTreeNode B) {
List<ParentTreeNode> pathA = retrace(A);
List<ParentTreeNode> pathB = retrace(B);
int indexA = pathA.size() - 1;
int indexB = pathB.size() - 1;
ParentTreeNode lca = null;
while(indexA >= 0 && indexB >= 0) {
if (pathA.get(indexA) != pathB.get(indexB))
break;
lca = pathA.get(indexA);
indexA--;
indexB--;
}
return lca;
}
private List<ParentTreeNode> retrace(ParentTreeNode node) {
List<ParentTreeNode> path = new ArrayList<>();
while (node != null) {
path.add(node);
node = node.parent;
}
return path;
}
}
// pathA: 3 4
// pathB: 5 7 4
// pathA: 5 7 4
// pathB: 6 7 4
