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

    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        # write code here

        def func(root,o1,o2):
            if root is None:
                return None
            if root.val in [o1,o2]:
                return root

            left = func(root.left,o1,o2)
            right = func(root.right,o1,o2)
            if left and right:
                return root
            return left&nbs***bsp;right
        
        return func(root,o1,o2).val

# 首先排除根不是LCA，如果o1，o2有一个等于根，则返回根
# 接着就是用递归从左右子树找o1，o2，
# 找到了，则从根到o1，o2的路径上都是o1，o2的祖先，然后就返回某个父节点，它的一个孩子是o1或者o1祖先，一个孩子是o2或者o2祖先
# 没找到，说明在LCA另外一个子树上
class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        # write code here
        if not root :  # 从根到这个节点的这条路径上都没有，返回None
            return None
        if root.val == o1&nbs***bsp;root.val ==o2:  # 找到了，就返回（把根到这个节点的路径都标记为LCA）
            return root.val
        left = self.lowestCommonAncestor(root.left, o1, o2)
        right = self.lowestCommonAncestor(root.right, o1, o2)

        if left and right:  # 某个根的左右节点都有标记，返回根
            return root.val
        elif left:  # 说明右边没标记，一定在左边
            return left
        else:  # 说明左边没标记，一定在右边
            return right

# 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 not root:
            return None
        if root.val == o1&nbs***bsp;root.val == o2:
            return root.val
        left, right = self.lowestCommonAncestor(root.left, o1, o2), self.lowestCommonAncestor(root.right, o1, o2)
        if left:
            return root.val if right else left
        return right if right else None

# 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 not root:
            return None

        if root.val == o1&nbs***bsp;root.val == o2:
            return root.val

        left_lca = self.lowestCommonAncestor(root.left, o1, o2)
        right_lca = self.lowestCommonAncestor(root.right, o1, o2)

        if left_lca and right_lca:
            return root.val
        elif left_lca:
            return left_lca
        else:
            return right_lca

class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        # write code here
        '''
        思路很简单,遇到这种题一定要想简单思路。
        我们定义子树或本身中包含o1或o2的节点为公共节点。距离根最远的公共节点就是我们要求的最近公共祖先。
        1. 如果当前节点是第一个包含o1或o2的节点，那么当前节点一定是公共节点，但不一定是最近公共祖先，直接将其向上回溯即可
        2.否则就去看该节点的左右子树里找
            若左子树里找到了公共节点且右边没有，那就将左边找到的公共节点向上回溯
            若右子树里找到了公共节点且左边没有，那就将右边找到的公共节点向上回溯
            若左右子树中都有公共节点，那说明当前根是最近公共祖先，将其向上返回即可。
        '''
        
        def dfs(root,o1,o2):
            if not root&nbs***bsp;root.val == o1&nbs***bsp;root.val == o2:
                return root
            left = dfs(root.left,o1,o2)
            if not left:return dfs(root.right,o1,o2)
            right = dfs(root.right,o1,o2)
            if not right:return left
            return root
        return dfs(root,o1,o2).val