Problem

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

The node has an extra attribute parent which point to the father of itself. The root's parent is null.

Example
For the following binary tree:

  4
 / \
3   7
   / \
  5   6
LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

思路

1. get all the parents of A and get all the parents of B separately as listA and listB

2. the top ancestor of both A and B is definitely root, which sits in the end of listA and listB, so scan from the end of both lists until we find the different node

    public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
                                                 ParentTreeNode A,
                                                 ParentTreeNode B) {
        // 1. get all the parents of A and get all the parents of B separately as listA and listB
        List<ParentTreeNode> la = getParents(A);
        List<ParentTreeNode> lb = getParents(B);
        // 2. the top ancestor of both A and B is definitely root, which sits in the end of listA and listB
        //      so scan from the end of both lists until we find the different node

        ParentTreeNode ans = null;

        int lenA = la.size();
        int lenB = lb.size();
        int indexA = lenA - 1;
        int indexB = lenB - 1;

        while (indexB >= 0 && indexA >= 0) {
            if (la.get(indexA) == lb.get(indexB)) {
                ans = la.get(indexA);
            } else {
                break;
            }
            indexA--;
            indexB--;
        }
        return ans;
    }

    private List<ParentTreeNode> getParents(ParentTreeNode node) {
        List<ParentTreeNode> result = new ArrayList<>();
        while (node != null) {
            result.add(node);
            node = node.parent;
        }
        return result;
    }

// version 2
    public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root, ParentTreeNode A, ParentTreeNode B) {
        if (A == null || B == null || root == null) return null;
        HashSet<ParentTreeNode> aParents = new HashSet<>();
        while (A != null) {
            aParents.add(A);
            A = A.parent;
        }
        while (B != null) {
            if (aParents.contains(B)) {
                return B;
            }
            B = B.parent;
        }
        return null;
    }