题解 | #在二叉树中找到两个节点的最近公共祖先#

from sys import flags
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @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)
        # 这里要注意重置一下标志
        self.flag = False
        self.dfs(root,path2,o2)
        # 从两个path中查找第一个相同节点
        # 注意，如果他们有相同的祖先，那么从前往后的路径一定是一样的
        i=0
        res = None
        while i < len(path1) and i<len(path2):
            if path1[i]==path2[i]:
                # 最后一个相同的节点就是最近的共同祖先，加一要放在后面
                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)
        # 查找判断是否有相同节点,找到就可以提前退出了
        # 这里设置一个标志，用于后面判断是否要返回路径
        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 因为传入的参数是随函数变化的
            return 
        # 否则就弹出，然后从父节点继续寻找
        # 这个回调很重要
        path.pop()