Lowest Common Ancestor II – Python 3 (Week 14 – 15)

 """
Definition of ParentTreeNode:
class ParentTreeNode:
    def __init__(self, val):
        self.val = val
        self.parent, self.left, self.right = None, None, None
"""


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
    """
    def lowestCommonAncestorII(self, root, A, B):
        # write your code here
        parentset = set()
        
        while A is not root:
            parentset.add(A)
            A = A.parent

        while B is not root:
            if B in parentset:
                return B
            B = B.parent

        return root