<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class TreeNode : <EOL> def __init__ ( self , val ) : <EOL> self . val = val <EOL> self . left , self . right = None , None <EOL> def __repr__ ( self ) : <EOL> return repr ( self . val ) <EOL> class Solution : <EOL> def lowestCommonAncestor ( self , root , A , B ) : <EOL> """<STR_LIT>""" <EOL> p1 = self . path ( root , A ) <EOL> p2 = self . path ( root , B ) <EOL> p1 . append ( TreeNode ( <NUM_LIT:0> ) ) <EOL> p2 . append ( TreeNode ( <NUM_LIT:0> ) ) <EOL> for ind , val in enumerate ( p1 ) : <EOL> if val != p2 [ ind ] : <EOL> return p1 [ ind - <NUM_LIT:1> ] <EOL> def path ( self , root , target ) : <EOL> """<STR_LIT>""" <EOL> ans = [ ] <EOL> self . get_path ( root , target , [ ] , ans ) <EOL> return ans <EOL> def get_path ( self , cur , target , path , ans ) : <EOL> """<STR_LIT>""" <EOL> if not cur : <EOL> return False <EOL> path . append ( cur ) <EOL> if cur == target : <EOL> ans . extend ( path ) <EOL> return True <EOL> if cur . left and self . get_path ( cur . left , target , path , ans ) : <EOL> return True <EOL> if cur . right and self . get_path ( cur . right , target , path , ans ) : <EOL> return True <EOL> path . pop ( ) <EOL> return False <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> node = TreeNode ( <NUM_LIT:1> ) <EOL> print Solution ( ) . lowestCommonAncestor ( node , node , node ) <EOL> nodes = dict ( zip ( range ( <NUM_LIT:3> , <NUM_LIT:8> ) , [ TreeNode ( i ) for i in range ( <NUM_LIT:3> , <NUM_LIT:8> ) ] ) ) <EOL> nodes [ <NUM_LIT:4> ] . left = nodes [ <NUM_LIT:3> ] <EOL> nodes [ <NUM_LIT:4> ] . right = nodes [ <NUM_LIT:7> ] <EOL> nodes [ <NUM_LIT:7> ] . left = nodes [ <NUM_LIT:5> ] <EOL> nodes [ <NUM_LIT:7> ] . right = nodes [ <NUM_LIT:6> ] <EOL> print Solution ( ) . lowestCommonAncestor ( nodes [ <NUM_LIT:4> ] , nodes [ <NUM_LIT:3> ] , nodes [ <NUM_LIT:5> ] ) </s>
