from sys import flags
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可
#
# 
# @param root TreeNode類 
# @param o1 int整型 
# @param o2 int整型 
# @return int整型
#
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        # write code here
        if root == None:
            return None
        path1 = []
        path2 = []
        self.dfs(root,path1,o1)
        # 這里要注意重置一下標(biāo)志
        self.flag = False
        self.dfs(root,path2,o2)
        # 從兩個(gè)path中查找第一個(gè)相同節(jié)點(diǎn)
        # 注意，如果他們有相同的祖先，那么從前往后的路徑一定是一樣的
        i=0
        res = None
        while i < len(path1) and i<len(path2):
            if path1[i]==path2[i]:
                # 最后一個(gè)相同的節(jié)點(diǎn)就是最近的共同祖先，加一要放在后面
                res = path1[i]
                i+=1
            else:
                break
        return res

        


    flag = False
    def dfs(self,root:TreeNode,path:list,m:int):
        if root == None:
            return
        path.append(root.val)
        # 查找判斷是否有相同節(jié)點(diǎn),找到就可以提前退出了
        # 這里設(shè)置一個(gè)標(biāo)志，用于后面判斷是否要返回路徑
        if root.val==m:
            self.flag = True
            return 
        self.dfs(root.left,path,m)
        self.dfs(root.right,path,m)
        # 如果存在一條這樣的路徑就返回
        if self.flag:
            # 這里可以不用return path 因?yàn)閭魅氲膮?shù)是隨函數(shù)變化的
            return 
        # 否則就彈出，然后從父節(jié)點(diǎn)繼續(xù)尋找
        # 這個(gè)回調(diào)很重要
        path.pop()