Python Recursive Solution to find ancestors


#1

#f=[]

def pre(A,c,f):

#global f
    
if A==None:
    return 0

if A.val==c:
    f.append(A.val)
    return 1

x=pre(A.left,c,f)

if x==1:
    f.append(A.val)
    return 1

y=pre(A.right,c,f)

if y==1:
    f.append(A.val)
    return 1

return 0

def sol(x,y):

d=dict()

for i in x:
    d[i]=1

for j in y:
    if j in d:
        return j

class Solution:
# @param A : root node of tree
# @param B : integer
# @param C : integer
# @return an integer
def lca(self, A, B, C):

    #global f
    f=[]
    
    p=pre(A,B,f)
    if p==0:
        return -1
    
    
    x=[]
    
    q=pre(A,C,x)
    
    if q==0:
        return -1
    
    #f.insert(0,B)
    
    #x.insert(0,C)
    
    #print(f,x)
    
    
    
    if B==C:
        return B
            
    flag=False
    
    if len(x)>=len(f):
        flag=True
    
    d=dict()
    if flag:
        
        return sol(f,x)
    else:
        return sol(x,f)