236. 二叉树的最近公共祖先

# 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':
        def dfs(root,tar,path):
            if not root:
                return False
            #在判断前就要append
            path.append(root)
            #深度优先，直接先遍历左子树
            if root == tar or dfs(root.left,tar,path) or dfs(root.right,tar,path):
                return True
            
            else:
                #当roo它本身不为tar，他的左子树中没有tar
                #右子树也有没tar时，root，一定不在路径中，所以pop
                path.pop()
                return False
        a,b = [],[]
        dfs(root,p,a)
        dfs(root,q,b)
        ans = None
        #路径第一个都是root，逐渐往后遍历。
        for i in range(min(len(a),len(b))):
            if a[i] == b[i]:
                ans = a[i]
        return ans