'''
Description: 
Autor: Au3C2
Date: 2021-03-24 17:08:40
LastEditors: Au3C2
LastEditTime: 2021-03-24 17:12:29
'''
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.maxLevel = 0
        self.ans = root
        self.p, self.q = p.val, q.val
        self.dfs(root,0)
        return self.ans

    def dfs(self,root,level):
            
        if not root:
            return False,False
                    
        leftp, leftq = self.dfs(root.left,level+1)
        rightp, rightq = self.dfs(root.right,level+1)
        
        flagp, flagq = False, False
        if root.val == self.p or leftp or rightp:
            flagp = True
        if root.val == self.q or leftq or rightq:
            flagq = True
        
        if flagp and flagq and self.maxLevel<level:
            self.maxLevel = level
            self.ans = root
            
        return flagp,flagq

# 树，中等。👆自己写的屑算法，不够简洁，看下面
# https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left: return right
        if not right: return left
        return root

# 主要是分析好多种情况，详情看下面👇
# https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/